Control.Generator1

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

In this code, we use a single global prompt (that is, ordinary shift0) Generator2.hs shows the need for several prompts.

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

type P m a = PS (Res 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.

newtype Res m a

Constructors

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

yield :: Monad m => a -> CC (P m a) m ()

in_order :: Monad m => Tree -> CC (P m Label) m ()

The enumerator: the for-loop essentially

The in_order function itself: compare with the Python version

test_io :: IO ()

Print out the result of the in-order traversal

test_st :: [Label]

Or return it as a pure list; the effects are encapsulated