http://www.perlmonks.org?node_id=520270


in reply to Re^4: Derangements iterator (callbacks)
in thread Derangements iterator

From enumerators to cursors: turning the left fold inside out...
The mechanical inversion procedure presented in * had a catch: it relies on shift/reset (or call/cc plus a mutable cell, which is the same thing). How can we do such an inversion in Haskell? We can introduce a right fold enumerator, which is more amenable to such transformations. Or we can use a continuation monad and emulate shift/reset. The present article demonstrates the third approach: a non-recursive left-fold. We argue that such a left fold is the best interface for a collection. Indeed, given the non-recursive left-fold we can:
  • instantiate it into the ordinary left fold
  • instantiate in into a stream
If we turn two enumerators into streams, we can *safely* interleave these streams.

We should point out that the relation between the left fold, the non-recursive left fold and the stream is deep. The ordinary, recursive left fold is the fix point of the non-recursive one. On the other hand, the instantiation of the non-recursive left fold as a stream, as we shall see, effectively captures a continuation in a monadic action. We see once again that call/cc and Y are indeed two sides of the same coin **.

The rest of the article demonstrates the inversion procedure. The procedure is generic, as evidenced by its polymorphic type. We illustrate the technique on an example of a file considered a collection of characters. Haskell provides a stream interface to that collection: hGetChar. We implement a left fold enumerator. We then turn that enumerator back to a stream: we implement a function 'myhgetchar' _only_ in terms of the left fold enumerator. The approach is general and uses no monadic heavy lifting.