Wed Sep 9 09:29:28 CEST 2009
I was wondering if it makes sense to allow infinite choice sequences.
Probably not, unless they appear at only one place in the tree. For
depth-first this should be on top, and for breath-first at the bottom.
Otherwise the infinite branching will prevent some children from ever
being reached. Also, allowing `cut' operations helps.
But, it does seem usefult to at least keep an algorithmic description
of choice points without having to resort to explicit lists.
Additionally, these choice points could be results from another search
problem, generated lazily..
So, what about reformulating choice as taking an enumerator by
default, instead of trying to shoe-horn procedural sequences back into
- lazyness is good
- enumerators (HOFs) are better than lazy lists (data structs)
So, `amb' takes a function. A choice point is then a continuation (a
hole) and an enumerator. The contination can be plugged into the
(struct choice (k enum)) -> (enum k)
Now, does this compose? I.e. can the driver just execute the
enumerator and nest the backtracking that way?
OK: settled to:
- amb takes enumerator
- some enumerator <-> list / stream / sequence transformers (enum.ss)
- solutions presented as enumerator
Marks should be installed at `amb' time, while cut