Skip to content

Instantly share code, notes, and snippets.

@joyofclojure
Forked from cgrand/gist:2302625
Created April 4, 2012 18:14
Show Gist options
  • Select an option

  • Save joyofclojure/2304384 to your computer and use it in GitHub Desktop.

Select an option

Save joyofclojure/2304384 to your computer and use it in GitHub Desktop.
fair conjunction notes
Streams were equipped with plus and bind, I removed bind and added join and narrow.
I also added yield which returns the yielded substitution map for the stream (if any)
and step which advances teh computation (was: calling the thunk).
join, like plus, interleaves execution of its two streams. As soon as one yields, the
yielded value is used to narrow the search space of the other stream.
For any stream A, we have:
A = (plus (yield A) (step A))
The interleaving formula behind join is:
(join A B) = (plus (narrow B (yield A)) (join B (step A))) ; interleaving on the join term
narrow is distributive over plus and join
(narrow (join A B)) = (join (narrow A) (narrow B))
(narrow (plus A B)) = (plus (narrow A) (narrow B))
Implementation detail
narrowed streams remember the substitutions map (the "min-yield") which was used to
narrow them so whole streams can be pruned if one tries to narrow a stream with a
substitution incompatible with its min-yield.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment