Stack-safe cartesian product

Help
#1

I’m trying to write a cartesian product function in Purescript.
To my surprise, this doesn’t seem to be stack-safe, it blows up with relatively small inputs:

cartesianProduct :: Array (Array Int) -> Array (Array Int)
cartesianProduct =
  Arr.foldl
    ( \b arr -> do
        x <- arr
        xs <- b
        [ Arr.snoc xs x ]
    )
    [ [] ]

xs = Arr.range 0 5 <#> \i -> do
  Arr.range 0 10 <#> \j -> j

result = cartesianProduct xs

-- RangeError: Maximum call stack size exceeded

However, this javascript implementation (which seems, in spirit, to be very similar) does not blow up. And it can in fact handle much larger inputs (though it’ll take a while to complete).

function cartesian(xs) {
  return xs.reduce(
    (a, b) => a.flatMap((x) => b.flatMap((y) => [[...x, y]])),
    [[]]
  );
}

let xs = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
cartesian([xs, xs, xs, xs, xs, xs]);

Why is the purescript version not stack safe and how can it be re-written to be stack safe?

#2

Unfortunately, this is because the ancient foreign implementation for Array’s bind isn’t safe because it uses apply as a micro optimization. Passing too many arguments via apply will result in a stack overflow in JS engines. The implementation for concat in purescript-arrays guards for this, but not prelude I guess.

1 Like
#3

Looks like this PR would fix it, but it seems stalled.
Similar to arrays’s concat implementation, but chunking the calls to .apply.

#4

At this point it should just use flatMap and fall back to a very simple implementation, likely. IMO the push/apply stuff is not worth it anymore.

1 Like
#5

What Nate said, but I’d also like to point out that in this case you don’t need bind, you only need apply which doesn’t suffer from the same problem -

ado
  x <- arr
  xs <- b
  in Arr.snoc xs x
1 Like