Control.Generator2

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).

Documentation

type Label = Int

A few preliminaries: define the tree and build a sample tree

data Tree

Constructors

Leaf

Node Label Tree Tree

Instances

Show Tree

make_full_tree :: Int -> Tree

newtype ResP m a

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

Constructors

ResP ((a -> CC PP m ()) -> CC PP m ())

Instances

Typeable1 m => Typeable1 (ResP m)

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

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 ()

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 ()

The enumerator: the for-loop essentially

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

The in_order function itself: compare with the Python version

test_ioP :: IO ()

Print out the result of the in-order traversal

newtype Res m a

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

Constructors

Res ((a -> CC (PM a) m ()) -> CC (PM a) m ())

Instances

Typeable1 m => Typeable1 (Res m)

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

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

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

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 ()

The enumerator: the for-loop essentially

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

The in_order function itself: compare with the Python version

test_io :: IO ()

Print out the result of the in-order traversal

newtype Acc a

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

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

Constructors

Acc [a]

Instances

Typeable1 Acc

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

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).

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

To avoid importing mtl, we define Identity on our own

Constructors

Identity

Fields

runIdentity :: a

Instances

Monad Identity

Typeable1 Identity