> I think you can "encode", or "mimick" every monad by the following type,
> which is the monad of continuations:
>
> type M a = (a -> Action) -> Action
>
[...]
> Unfortunately the Haskell type system is often too restrictive to encode
> the wanted features. I have for example no idea how to do lists in this
> setting, without doing dirty type hacks in Haskell (but it _is_
> possible... :-).
You need second-order types or local universal quantification. First
note that
> type M a = forall action. (a -> action) -> action
is essentially isomorphic to `a'. A monad capable of backtracking is
obtained via
> type M a = forall action. (a -> action -> action) -> action -> action
We can even turn it into a backtracking monad transformer:
> type T m a = forall action. (a -> m action -> m action) -> m action -> m action
For more information see my FLOPS'98 paper.
Cheers, Ralf
@inproceedings{Hin98Pro,
address = {Singapore, New Jersey, London, Hong Kong},
author = {Hinze, Ralf},
booktitle = {Third Fuji International Symposium on Functional and Logic
Programming (FLOPS98)},
month = apr,
publisher = {World Scientific},
title = {Prological Features in a Functional Setting --- Axioms and
Implementations},
year = 1998
}
