liboleg-2010.1.9.0: An evolving collection of Oleg Kiselyov's Haskell modules



Generators in Haskell

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

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

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



type Label = IntSource

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

data Tree Source


Node Label Tree Tree 


type P m a = PS (Res m a)Source

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 Source


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

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

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

The enumerator: the for-loop essentially

The in_order function itself: compare with the Python version

test_io :: IO ()Source

Print out the result of the in-order traversal

test_st :: [Label]Source

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