These notes may change in the next few days (today is 30 Nov 2010).
The material here benefited from many discussions with Ken Shan.
-[[!toc]]
+##[[Tree and List Zippers]]##
-##List Zippers##
+##[[Coroutines and Aborts]]##
-Say you've got some moderately-complex function for searching through a list, for example:
-
- let find_nth (test : 'a -> bool) (n : int) (lst : 'a list) : (int * 'a) ->
- let rec helper (position : int) n lst =
- match lst with
- | [] -> failwith "not found"
- | x :: xs when test x -> (if n = 1
- then (position, x)
- else helper (position + 1) (n - 1) xs
- )
- | x :: xs -> helper (position + 1) n xs
- in helper 0 n lst;;
+##[[From Lists to Continuations]]##
This searches for the `n`th element of a list that satisfies the predicate `test`, and returns a pair containing the position of that element, and the element itself. Good. But now what if you wanted to retrieve a different kind of information, such as the `n`th element matching `test`, together with its preceding and succeeding elements? In a real situation, you'd want to develop some good strategy for reporting when the target element doesn't have a predecessor and successor; but we'll just simplify here and report them as having some default value:
that is intended to
represent non-deterministic computations as a tree.
+##[[List Monad as Continuation Monad]]##
+
+##[[Manipulating Trees with Monads]]##