Skip to content

Instantly share code, notes, and snippets.

@puffnfresh

puffnfresh/non-strict-vs-strict.md

Last active January 4, 2016 04:59
Show Gist options
  • Save puffnfresh/b957e76d84cf3f89d603 to your computer and use it in GitHub Desktop.
Save puffnfresh/b957e76d84cf3f89d603 to your computer and use it in GitHub Desktop.
Download ZIP
Comparison of lazy vs strict Free
Raw
non-strict-vs-strict.md

Free in Haskell:

data Free f a = Return a
              | Suspend (f (Free f a))

Free in a strict language:

data Free f a = Return a
              | Suspend (f (Free f a))
              | Gosub (forall s. (forall r. ({} -> Free f r) -> (r -> Free f a) -> s) -> s)

The additional Gosub constructor is required to create a reassociating trampoline so that we can write a tail recursive run function, otherwise we're gonna blow the stack!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment