Mon May 10 14:24:05 EDT 2010
Syntax directed vs. Semantics directed (fold vs. monad)
Merging monads and folds for functional programming.
For this Scheme nut & Haskell noob, the more interesting remarks are
in the introduction which uses some terminology I wasn't familiar
folds - syntax directed - organize on input types
monads - semantics directed - organize on output types
Here "syntax" refers to the structure of the data types. Generalized
folds can be constructed systematically by replacing constructors with
functions. (I.e. for the list constructor Nil this is a 0-argument
function or a value).
I briefly skimmed the paper; the basic idea seems to be that it's
possible to define fold-like operators for monads and have the best of
Now I think I also understand why I have a natural affinity towards
the fold approach, and have difficulty thinking in monads:
* Scheme is strict and impure; monads are not really necessary.
It's often useful to combine context/state with fold/map
operations which are easy to express.
* To a lesser extent, in a dynamically typed language, polymorphism
can be used dispatching on inputs, while a statically typed
language can dispatch on outputs. This is why types + monads go
One thing I'm interested in more is a monadic map, i.e. something that
lifts (s,i)->(s,o) to (s,[i])->(s,[o]). How this this fit the bill?
As a special case of monadic fold?