On 7/9/09, Heinrich Apfelmus apfel...@quantentunnel.de wrote:
Of course, some part of algorithm has to be recursive, but this can be
outsourced to a general recursion scheme, like the hylomorphism
hylo :: Functor f = (a - f a) - (f b - b) - (a - b)
hylo f g = g . fmap (hylo f g) . f
Raynor Vliegendhart wrote:
On 7/9/09, Heinrich Apfelmus apfel...@quantentunnel.de wrote:
Of course, some part of algorithm has to be recursive, but this can be
outsourced to a general recursion scheme, like the hylomorphism
hylo :: Functor f = (a - f a) - (f b - b) - (a - b)
hylo f g =
Matthias Görgens wrote:
Thanks. I heard about the hylo-, ana- and catamorphisms before, but
never explicitly used them. Time to get started.
You did use them explicitly :) , namely in
treeSort = bootstrap partitionOnMedian
bootstrap f = Fix . helper . f
where helper = fmap (Fix .
Interesting. Can you make the definition of quicksort non-recursive,
too? Perhaps with help of a bootstrapping combinator like the one
implicit in the approach I have given earlier?
treeSort = bootstrap partitionOnMedian
bootstrap f = Fix . helper . f
where helper = fmap (Fix . helper .
Matthias Görgens wrote:
Interesting. Can you make the definition of quicksort non-recursive,
too? Perhaps with help of a bootstrapping combinator like the one
implicit in the approach I have given earlier?
treeSort = bootstrap partitionOnMedian
bootstrap f = Fix . helper . f
where
Thanks. I heard about the hylo-, ana- and catamorphisms before, but
never explicitly used them. Time to get started.
And yet another question: One can get the median in deterministic
linear time. For quicksort choosing the median as pivot keeps the O(n
log n) average running time and brings
Matthias Görgens wrote:
So, a tree like Matthias implements it is the way to go. Basically, it
reifies the recursive calls of quicksort as a lazy data struture which
can be evaluated piecemeal.
Yes. I wonder if it is possible to use a standard (randomized
quicksort) and employ some type
Petr Pudlak wrote:
about a month ago, we were discussing sorting in Haskell with a friend. We
realized a nice property of lazy merge-sort (which is AFAIK the implementation
of Data.List.sort): Getting the first element of the sorted list actually
requires O(n) time, not O(n * log n) as in
So, a tree like Matthias implements it is the way to go. Basically, it
reifies the recursive calls of quicksort as a lazy data struture which
can be evaluated piecemeal.
Yes. I wonder if it is possible to use a standard (randomized
quicksort) and employ some type class magic (like
