safareli/free

Problem with ap / foldMap and stack safety ?

Closed this issue · 4 comments

kozak commented

Hi Safareli - thank you for your great work on Free. I've tried to base my ruby implementation on yours, and run into an issue with stack safety when using ap / foldMap.

Specifically: I've modified your 'Is stack safe' test:

const sum = require('ramda/src/sum')
const { sequence } = require('sanctuary-type-classes')

test('Is stack safe ap', t => {
  const times = 10000
  const array = Array(times).fill(Free.liftF(1))
  const result = sequence(Free.of, array).map(sum)

  t.equals(result.foldMap(Identity.of, Identity).get(), times, 'Works with Identity')

  t.end()
})

Ends up in an error RangeError: Maximum call stack size exceeded when times gets bigger.
Will be looking at this more today.

safareli commented

I think sanctuary-js/sanctuary-type-classes#19 is related, and after the PR is merged and sanctuary-type-classes updated this problem should go away. will take a closer look at it after #31

Thanks!

safareli commented

also current version is not lawful, (ap should be derived from chain). and in the PR i mentioned we would have lawful version of Free monad which should not have the issue as ap would be derived from chain and when you fold such structure chainRec is used which must be stack safe.

even tho I would try to make sure Free applicative has no such issues.

kozak commented

Thanks! I've modified ap and map to use chain (based on purescript-free) and now the test pass, even thought it takes quite a lot of time to complete.

safareli commented

This should be fixed in recent dev branch.
Also the FreeApplicative (Par) provided here is stack safe too.

  • 🎉1