Document (or fix) stack safety issues

[milesfrain]

Some example of existing stack-unsafe functions:

• sort - reported in #192
• nubEq, can be fixed for strict lists by applying same strategy used for struct nub in #179
• nub for lazy lists. Don't know of a good way to fix this. The strict nub strategy of #179 cannot be applied here because you can't reverse an infinite lazy list.

We should ideally setup stack-safety tests for every function. To help make those tests run faster, we could shrink the v8 stack size with something like --stack_size=10 (default is 984 kB).

[hdgarrood]

I would prefer that we test with lists which are large enough to blow the stack than shrink the stack artificially, as we ideally ought to be testing with large inputs anyway, e.g. so that we are more likely to notice if we make a change which unintentionally makes some functions much slower for large inputs.

[imcotton]

From Data.List.Lazy

• elemIndex
• elemLastIndex
• findLastIndex
• findIndex <--- caused by

purescript-lists/src/Data/List/Lazy.purs

Lines 317 to 327 in 6383c4f

	-- | Find the first index for which a predicate holds.
	findIndex :: forall a. (a -> Boolean) -> List a -> Maybe Int
	findIndex fn = go 0
	where
	go :: Int -> List a -> Maybe Int
	go n list = do
	o <- uncons list
	if fn o.head
	then pure n
	else go (n + 1) o.tail

[elldritch]

group also does not appear to be stack-safe.

[elldritch]

It appears that concat is also not stack-safe?

[garyb]

Yeah, seems so - concat is implemented with bind which isn't stack safe:

purescript-lists/src/Data/List/Types.purs

Lines 165 to 167 in 68bce83

	instance bindList :: Bind List where
	bind Nil _ = Nil
	bind (x : xs) f = f x <> bind xs f