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