Generators in Haskell

We translate the in-order tree traversal example from an old article Generators in Icon, Python, and Scheme, 2004.

http://okmij.org/ftp/Scheme/enumerators-callcc.html#Generators

using Haskell and delimited continuations rather than call/cc + mutation. The code is shorter, and it even types. To be honest, we actually translate the OCaml code generator.ml

This code is the extension of Generator1.hs; we use delimited control not only to implement the generator. We also use delimited control to accumulate the results in a list. We need two different prompts then (with two different answer-types, as it happens). This file illustrates the prompt flavors PP and PM, using newtypes to define private global prompts (global prompts that are private to the current module).

- type Label = Int
- data Tree
- make_full_tree :: Int -> Tree
- newtype ResP m a = ResP ((a -> CC PP m ()) -> CC PP m ())
- ppy :: (Typeable1 m, Typeable a) => Prompt PP m (ResP m a)
- yieldP :: (Typeable1 m, Typeable a) => Monad m => a -> CC PP m ()
- enumerateP :: (Typeable1 m, Typeable a, Monad m) => CC PP m () -> (a -> CC PP m ()) -> CC PP m ()
- in_orderP :: (Typeable1 m, Monad m) => Tree -> CC PP m ()
- test_ioP :: IO ()
- newtype Res m a = Res ((a -> CC (PM a) m ()) -> CC (PM a) m ())
- py :: (Typeable1 m, Typeable a) => Prompt (PM a) m (Res m a)
- yield :: (Typeable1 m, Typeable a) => Monad m => a -> CC (PM a) m ()
- enumerate :: (Typeable1 m, Typeable a, Monad m) => CC (PM a) m () -> (a -> CC (PM a) m ()) -> CC (PM a) m ()
- in_order :: (Typeable1 m, Monad m) => Tree -> CC (PM Label) m ()
- test_io :: IO ()
- newtype Acc a = Acc [a]
- pa :: Typeable a => Prompt (PM a) m (Acc a)
- acc :: (Typeable a, Monad m) => a -> CC (PM a) m ()
- accumulated :: (Typeable a, Monad m) => CC (PM a) m () -> CC (PM a) m [a]
- test_acc :: [Label]
- newtype Identity a = Identity {
- runIdentity :: a

# Documentation

make_full_tree :: Int -> TreeSource

In Python, `yield`

is a keyword. In Haskell, it is a regular function.
Furthermore, it is a user-defined function, in one line of code.
To get generators there is no need to extend a language.

First, we try the prompt flavor PP

The answer-type for one of the prompts

ppy :: (Typeable1 m, Typeable a) => Prompt PP m (ResP m a)Source

One prompt, used by the generator (the yield/enumerate pair) We instantiate the global pp to the desired answer-type.

yieldP :: (Typeable1 m, Typeable a) => Monad m => a -> CC PP m ()Source

The rest of the code, up to test_io, is the same as that in Generator1.hs

enumerateP :: (Typeable1 m, Typeable a, Monad m) => CC PP m () -> (a -> CC PP m ()) -> CC PP m ()Source

The enumerator: the for-loop essentially

in_orderP :: (Typeable1 m, Monad m) => Tree -> CC PP m ()Source

The in_order function itself: compare with the Python version

Using the prompt flavor PM

The above code works. We can define the second pair of operators
to accummulate the result into a list. Yet, the solution is
not very satisfactory. We notice that the prompt type ppy is
polymorphic over a, the elements we yield. What ensures that
`yieldP`

yields elements of the same type that enumerateP can pass to the
body of the loop? Nothing, actually, at compile time. If yieldP and
enumerateP do not agree on the type of the elements, a run-time
error will occur.
This is where the PM prompt type comes in handy. It has a phantom
type parameter c, which can be used to communicate between
producers and consumers of the effect. We use the type parameter c
to communicate the type of elements, between yield and enumerate.
Since the parameter is phantom, it costs us nothing at run-time.

The answer-type for one of the prompts

py :: (Typeable1 m, Typeable a) => Prompt (PM a) m (Res m a)Source

One prompt, used by the generator (the yield/enumerate pair)

yield :: (Typeable1 m, Typeable a) => Monad m => a -> CC (PM a) m ()Source

The rest of the code, up to test_io, is the same as that in Generator1.hs

enumerate :: (Typeable1 m, Typeable a, Monad m) => CC (PM a) m () -> (a -> CC (PM a) m ()) -> CC (PM a) m ()Source

The enumerator: the for-loop essentially

in_order :: (Typeable1 m, Monad m) => Tree -> CC (PM Label) m ()Source

The in_order function itself: compare with the Python version

The second application of control: accumulating the results in a list

The answer-type for the second prompt. We use newtype for identification

Acc [a] |

pa :: Typeable a => Prompt (PM a) m (Acc a)Source

The second prompt, used by the acc/accumulated pair
Again we use the mark of PM to communicate the type of the elements
between `acc`

and `accumulated`

. It happens to be the same type used
by yield/enumetrate.
If that was not the case, we could have easily arranged for a type-level
record (see HList or the TFP paper).