search

hdgarrood / purescript-sequences

Various efficient-ish sequence types for PureScript.
http://pursuit.purescript.org/packages/purescript-sequences
MIT License
45 stars 22 forks source link

fromSeq can exceed maximum stack size when converting large sequence to `List` #20

Closed rgrempel closed 8 years ago

rgrempel commented 8 years ago

I was using fromSeq to convert from large sequences to lists, and ran into problems with the stack size:

import Prelude
let bob = Data.Sequence.toSeq $ Data.Array.range 0 32768

Data.Sequence.length bob
-- 32769

Data.List.length $ Data.Sequence.fromSeq bob

{-
/Users/rgrempel/projects/purescript/elm/.psci_modules/node_modules/Data.Array/foreign.js:197
      return l.slice(s, e);
               ^
RangeError: Maximum call stack size exceeded
    at /Users/rgrempel/projects/purescript/elm/.psci_modules/node_modules/Data.Array/foreign.js:197:16
    at tail (/Users/rgrempel/projects/purescript/elm/.psci_modules/node_modules/Data.Array.Unsafe/index.js:19:54)
    at Defer.thunk (/Users/rgrempel/projects/purescript/elm/.psci_modules/node_modules/Data.FingerTree/index.js:540:72)
    at Defer.exports.defer.Defer.force (/Users/rgrempel/projects/purescript/elm/.psci_modules/node_modules/Data.Lazy/foreign.js:18:22)
    at Object.exports.force (/Users/rgrempel/projects/purescript/elm/.psci_modules/node_modules/Data.Lazy/foreign.js:31:12)
    at /Users/rgrempel/projects/purescript/elm/.psci_modules/node_modules/Data.FingerTree/index.js:553:84
    at Defer.thunk (/Users/rgrempel/projects/purescript/elm/.psci_modules/node_modules/Data.FingerTree/index.js:540:106)
    at Defer.exports.defer.Defer.force (/Users/rgrempel/projects/purescript/elm/.psci_modules/node_modules/Data.Lazy/foreign.js:18:22)
    at Object.exports.force (/Users/rgrempel/projects/purescript/elm/.psci_modules/node_modules/Data.Lazy/foreign.js:31:12)
    at step (/Users/rgrempel/projects/purescript/elm/.psci_modules/node_modules/Data.FingerTree/index.js:664:92)
    at go (/Users/rgrempel/projects/purescript/elm/.psci_modules/node_modules/Data.List/index.js:88:55)
-}

However, an alternative approach with foldr works fine:

let list = Data.Foldable.foldr Data.List.Cons Data.List.Nil bob
Data.List.length list

-- 32769

Just as an experiment, I tried implementing fromSeq as unfoldr uncons. This works, but has the same problem with stack size.

Now, I think this suggests that the problem is either in Unfoldable or in the implementation of Unfoldable in List -- not in Data.Sequence as such. However, I'm new to Purescript, so I could easily be interpreting all of this inaccurately.

In fact, I just tried fromSeq to convert to a large Data.Array instead of a large Data.List, and that works fine.

import Prelude
let bob = Data.Sequence.toSeq $ Data.Array.range 0 32768

Data.Sequence.length bob
-- 32769

Data.Array.length $ Data.Sequence.fromSeq bob
-- 32769

So, I guess the problem is in Data.List? If so, feel free to close this issue.

hdgarrood commented 8 years ago

I'm not really sure, but it does sound like the problem might be in the Unfoldable List instance; that's where I'd start looking. I'll leave this open for now, though.

rgrempel commented 8 years ago

Here's the unfoldableList implementation ...

instance unfoldableList :: Unfoldable List where
  unfoldr f b = go (f b)
    where
    go Nothing = Nil
    go (Just (Tuple a b)) = Cons a (go (f b))

Now, I think the recursive call to go must be the problem ... it doesn't look properly tail-recursive to me. I'll play with this a bit and see if I can fix it.

hdgarrood commented 8 years ago

Yep, that's correct: it isn't, because of the call to Cons on the last line.

rgrempel commented 8 years ago

I submitted a PR in purescript-lists, so I'll close this here.