Jello_Raptor 2017-02-10 12:47:21
glguy: yup, I'm doing basically that now, it's a lot nicer than the kludge I had before
jmg8766 2017-02-10 12:49:16
if ++ takes linear time? then does that mean the examples of sorts that use it are really slow? like quicksort = quicksort smaller ++ pivot ++ quicksort larger ?
merijn 2017-02-10 12:49:45
jmg8766: The "standard" quicksort example is pretty awful, yes
merijn 2017-02-10 12:50:00
jmg8766: The actual sort GHC uses is an optimised merge sort
jmg8766 2017-02-10 12:50:09
merijn okay I knew it thanks
merijn 2017-02-10 12:50:51
jmg8766: The GHC source has a bunch of comments and older sort implementations discussing performance: https://hackage.haskell.org/package/base-4.9.1.0/docs/src/Data.OldList.html#sort
monochrom 2017-02-10 12:51:14
With ++ linear time, I think qsort is still n log n on average.
merijn 2017-02-10 12:51:39
Could be, but it certainly doesn't help your constants
monochrom 2017-02-10 12:52:16
It's basically n log n + 3n vs n log n + 2n or something.
geekosaur 2017-02-10 12:52:17
worth remembering is that a lot of the "canonical" examples, including those in the Report, are tutelary in nature
geekosaur 2017-02-10 12:52:46
implementations are expected to match them with respect to laziness but not necessarily with respect to asymptotics
monochrom 2017-02-10 12:53:36
Also the optimized merge sort has the dual problem of taking linear time to cut a list into two halves.
dolio 2017-02-10 12:53:53
It's not that kind of merge sort.
merijn 2017-02-10 12:54:24
monochrom: It doesn't really bother repeatedly dividing
dolio 2017-02-10 12:55:59
It has to concatenate lists, though.
dolio 2017-02-10 13:05:28
Or rather, it has to merge them, which can involve rebuilding both lists, instead of just one.
dolio 2017-02-10 13:06:32
So perhaps you should consider why you'd worry about quick sort without being worried about merge sort.
monochrom 2017-02-10 13:11:15
Yes, my main point as well.
xcmw 2017-02-10 13:30:50
What is the best dom frp library?
jmg8766 2017-02-10 13:31:36
will (filter (=) xs) have linear time?
monochrom 2017-02-10 13:35:47
Yes.
monochrom 2017-02-10 13:36:42
reflex-dom may be a good dom frp library
xcmw 2017-02-10 13:38:20
monochrom: Ok. That was the one I was planing to use.
monochrom 2017-02-10 13:39:41
Cale uses it for work. You may like to ask him more.
xcmw 2017-02-10 13:42:04
monochrom: Do you how to install reflex for use with stack?
monochrom 2017-02-10 13:42:14
No.
