Mon May 10 14:24:05 EDT 2010

Syntax directed vs. Semantics directed (fold vs. monad)

Merging monads and folds for functional programming[1].

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
both worlds.

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
     well together.

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?

[1] http://www.springerlink.com/index/768043006044675P.pdf
[2] http://www.haskell.org/ghc/docs/6.12.1/html/libraries/base/Data-Foldable.html