# Re: Icon


Date: Fri, 21 Dec 2001 02:53:02 +0200
From: Lauri Alanko <la@iki.fi>

On Thu, Dec 20, 2001 at 06:09:52PM -0500, Guy Steele wrote:
> See?  it's easy!  :-)

Yes, this is very nice!  One way to look at a Monad is that
it provides a way to map whatever data structure is being
used as a "result value" into some other kind of data structure
(plus providing a useful algebra on such data structures).
Of course, the "data structure" might be a function.

\begin{code}
module M where

-- use some standard monad combinators

-- define the monad type, which is precisely of the form Guy described.
-- Here r is a type parameter for the ultimate return value, and a is
-- the type of value that this M will generate.
newtype M r a = M { runM :: (a -> r -> r) -> r -> r }

I think you are able to identify "failure continuation"
with "result value" because Haskell is lazy.  In an eager
language, wouldn't the signature be more like

runM :: (a -> r -> r) -> (() -> r) -> r

?

-- make it a monad, meaning:
-- a pure value is converted to an M by applying the success
-- continuation to it
return x = M (\sc -> sc x)
-- when we want to operate on an M, we simply apply it to a success
-- continuation that applies the function
M m >>= f = M (\sc -> m (\x -> runM (f x) sc))

-- A failure means simply returning the failure value
mzero = M (\sc fc -> fc)
-- while combining two Ms means giving one's return value as the other's
-- failure argument (. means function composition)

More precisely (or, in an eager language), the failure continuation of one
is a computation () -> r that will evaluate the other?

M m mplus M m' = M (\sc -> m sc . m' sc)

despite the fact that it is not obvious at first (and I half
thought there was an error here), mzero is indeed a left identity
as well as a right identity for mplus!

-- Some silly cruft to use numerical operations conveniently
instance (Num n) => Eq (M r n)
instance (Num n) => Show (M r n)
instance (Num n) => Num (M r n) where
(+) = liftM2 (+)

-- A set of values is defined by making each of the pure values an M (by
-- return), and then combining them with mplus (msum = foldl mplus mzero)

to lower upper = msum (map return [lower..upper])

\end{code}

This technique is described in detail in Ralf Hinze's ICFP 2000 paper
<http://citeseer.nj.nec.com/hinze00deriving.html>.

Here's an example:

M> runM (to 1 3 + to 4 6) (:) []
[5,6,7,6,7,8,7,8,9]

Here we used list construction as the way to combine values. Another
option:

M> runM (to 1 3 + to 4 6) (\a b -> print a >> b) (return ())
5
6
7
6
7
8
7
8
9

Here we use first-class IO actions as the return value, which is a

Note that there is no need for any syntax transformations, this is pure
everything is a first-class value...

A similar thing might be achieved in Lisp by decreeing that
every function must return a pair of a value and a failure
continuation.  But enforcing this decree would be difficult.
Haskell's polymorphic inferred type system is at once dictatorial
and unobtrusive.

--Guy



• Follow-Ups:
• Re: Icon
• From: Lauri Alanko <la@iki.fi>