Attempting to sort a 80000 element list gives a stack overflow error.

[ghost]

I am new to PureScript and to learn it, I was implementing a solution to this problem: Project Euler 694. Guess what, when I tried to sort a list (Data.List.sort) of BigInts with about 80000 elements in it, the program crashed with stack out of memory error. So, I worked around it by converting the list to an array, sorting the array and converting the array back to a list.

Also, to wield my new found knowledge of PureScript, I implemented a merge-sort in purescript with a tail-recursive merge function. With this implementation of sort, the program ran successfully without any stack overflow errors. The code for the merge sort is available here: Merge Sort. Could someone replace the implementation of Data.List.sort with the above implementation so that we do not get any stack overflow errors for even modestly large size lists.

[hdgarrood]

Thanks for the report! Your implementation isn't quite suitable as it is right now: at the moment it only works on lists of BigInts, but we'd want it to have the type

forall a. Ord a => List a -> List a

It may also be worth doing some benchmarking to verify that this implementation is in fact faster than just converting to Array, using Array's sort, and converting back again.

[ghost]

Agreed. I know the merge-sort works only for BigInt's, I have not figured out generics for purescript yet, and do not know how to use generic compare functions. So, when I meant replace, I meant obviously to generify the above code and replace the Data.List.sort with it. The problem is not speed, the problem is the stack-out-of-memory error.