sort and sortBy are not stack safe

[milesfrain]

sort $ range 1 1000000

/home/miles/projects/purescript/lists/output/Data.List/index.js:287
                            return as(new Data_List_Types.Cons(a, ys));
                                      ^
RangeError: Maximum call stack size exceeded
    at $tco_var_as (/home/miles/projects/purescript/lists/output/Data.List/index.js:287:39)

Should we swap out this current version (which I assume depends on Haskell's laziness) for something that just reuses Array's sortBy? I think that might end up being faster even in situations where we're not having stack issues.

https://github.com/purescript/purescript-lists/blob/6d8e30eeb9714bc422b6fb75ad1b0f43bef59703/src/Data/List.purs#L447-L482

[milesfrain]

I'm thinking something like this would work:

sortBy :: forall a. (a -> a -> Ordering) -> List a -> List a
sortBy cmp = fromFoldable <<< Array.sortBy cmp <<< Array.fromFoldable

But it's very slow. It should be much faster if we change Array.fromFoldable to use foldl instead. Here's the existing version:

fromFoldable :: forall f. Foldable f => f ~> Array
fromFoldable = fromFoldableImpl foldr

https://github.com/purescript/purescript-arrays/blob/463dcacb99455de5e28ac4a3312bb795f293d2d9/src/Data/Array.purs#L154-L155

---

Edit: Another option, but still slower than the original list version (up to 10k elements, then list version overflows).

sortBy :: forall a. (a -> a -> Ordering) -> List a -> List a
sortBy cmp = fromFoldable <<< Array.sortBy cmp <<< toUnfoldable

[hdgarrood]

Have you benchmarked what effect it would have by swapping fromFoldable to use foldl rather than foldr?

[hdgarrood]

FYI the Haskell version depends more on the GHC runtime being smarter about stack usage, which is separate from laziness. In Haskell it’s very rare that you have to worry about stack overflows, because of how the GHC runtime works.

[elldritch]

I just ran into this while solving Advent of Code. Any recommended workarounds in the meantime?