On 16 September 2013 18:35, Florian Lammel wrote:

Hi,

Hi Florian,

I've just started learning Haskell and am trying to implement some basic algorithms.

I'm a beginner in Haskell as well so my advice may be corrected by someone else :)

My shot at merge sort looks like this:

mergeSort :: Ord a => [a] -> [a] mergeSort [] = [] mergeSort [x] = [x] mergeSort xs = merge (mergeSort as) (mergeSort bs) where (as, bs) = splitInHalf xs

splitInHalf :: [a] -> ([a], [a]) splitInHalf [] = ([], []) splitInHalf [x] = ([x], []) splitInHalf (x:y:xys) = (x:xs, y:ys) where (xs, ys) = splitInHalf xys

merge :: Ord a => [a] -> [a] -> [a] merge xs [] = xs merge [] ys = ys merge (x:xs) (y:ys) = if x < y then x:(merge xs (y:ys)) else y:(merge ys (x:xs))

As far as I can tell, my implementation is more or less the same as on rosetta code [0], literate programs [1] and several stack overflow questions [2][3].

Well actually the Rosetta code link shows 3 different implementations and yours is the first of the three. Did you try the second one (the bottom up merge)? This is also what's used in the answer to the SO post [3] and according to the author there it's roughly what's used by ghc for Data.List.sort so it's presumably a good algorithm.

The algorithm works, but for large lists (for example, 500k random numbers), I get a stack overflow.

I'm not sure how this gets optimised but your call-stack is essentially as long as the input list. That's only going to work with such big inputs if the recursion is somehow optimised which I think happens because of lazy evaluation. However this depends on your merge function pulling a similar number of items from the 'as' list as from the 'bs' list. Otherwise (I think) you'll have a whole load of splitInHalf frames in the stack and maybe that gives your overflow. I may be *entirely* wrong but I think the problem comes from returning two lists from a function as you do in splitInHalf but then not consuming the same number of items from each at any one time. I don't think this can be optimised in quite the same lazy manner. It would be fine if you consumed from both lists in unison as in e.g. a merge-sum algorithm.

So my question is: How can I change my code so that it works on larger inputs? Or, more generally, how can I write recursive algorithms in functional languages that require more nested function calls than fit in the stack?

Have you tried the other algorithm from e..g Rosetta code? That one looks like it would work better in a lazy evaluation context since it just works sequentially on a list of lists. Oscar

I an iterative solution works much better. Here's an example, using your merge function. mergeSort1 :: Ord a => [a] -> [a] mergeSort1 = go . map (:[]) where go [] = [] go [xs] = xs go xss = go (mergePairs xss) mergePairs (xs:ys:pairs) = merge xs ys : mergePairs pairs mergePairs pairs = pairs h> :!ghc -O2 Merge -fforce-recomp [1 of 1] Compiling Merge ( Merge.hs, Merge.o ) h> :m + Data.List h> :load Merge Ok, modules loaded: Merge. h> :set +s h> length $ let n = 1000000 in mergeSort [n, n-1 .. 1] 1000000 (5.15 secs, 2924212128 bytes) h> length $ let n = 1000000 in mergeSort1 [n, n-1 .. 1] 1000000 (1.58 secs, 1027356744 bytes) h> length $ let n = 1000000 in sort [n, n-1 .. 1] 1000000 (0.24 secs, 107481296 bytes) The source to Data.List's sort is clever, you should give it a read: http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/Data-List.htm... On Mon, Sep 16, 2013 at 10:35 AM, Florian Lammel wrote:

Hi,

I've just started learning Haskell and am trying to implement some basic algorithms. My shot at merge sort looks like this:

mergeSort :: Ord a => [a] -> [a] mergeSort [] = [] mergeSort [x] = [x] mergeSort xs = merge (mergeSort as) (mergeSort bs) where (as, bs) = splitInHalf xs

splitInHalf :: [a] -> ([a], [a]) splitInHalf [] = ([], []) splitInHalf [x] = ([x], []) splitInHalf (x:y:xys) = (x:xs, y:ys) where (xs, ys) = splitInHalf xys

merge :: Ord a => [a] -> [a] -> [a] merge xs [] = xs merge [] ys = ys merge (x:xs) (y:ys) = if x < y then x:(merge xs (y:ys)) else y:(merge ys (x:xs))

As far as I can tell, my implementation is more or less the same as on rosetta code [0], literate programs [1] and several stack overflow questions [2][3].

The algorithm works, but for large lists (for example, 500k random numbers), I get a stack overflow.

So my question is: How can I change my code so that it works on larger inputs? Or, more generally, how can I write recursive algorithms in functional languages that require more nested function calls than fit in the stack?

Regards Florian

[0] http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Haskell [1] http://en.literateprograms.org/Merge_sort_(Haskell) [2] http://stackoverflow.com/questions/7554226/haskell-merge-sort-sorting-words-... [3] http://stackoverflow.com/questions/1215432/merge-sort-in-haskell

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners