[Haskell-cafe] Re: Lists vs. Monads

[oleg at pobox.com]

Jonathan Cast wrote:

> > If  you had  a version  of Haskell  without recursive  data  types you
> > wouldn't be at a loss, because you could always use monads to recreate
> > lists.   Maybe "bind"  would replace  the job  of "cons"  and "return"
> > would replace "head" or somesuch.

> No.   You  can't  define  most  initial  models  without  recursive  (or
> inductive)  data types in  general, because  initial models  are defined
> inductively.
...
> You can't define head, tail, or foldr using the MonadPlus signature (how
> would you  define them for e.g.   a backtracking parser?),  which is why
> you  do need  recursive types  for  [] 

However surprising might it seem, you _can_ define head, tail, and
foldr for an implementation of a backtracking transformer that it is
not a list and uses no recursive (or inductive) types. In fact, it is
possible to define list final algebra (complete with head and tail) in
a language without recursive datatypes, only with the higher-rank
one. The msplit contraption of the LogicT paper was `null', `head',
and `tail' all in one. The paper specifically made a point that msplit
can be defined without help from recursive data types.  The brief
summary of that derivation is a note `How to take a TAIL of a
functional stream'

	http://pobox.com/~oleg/ftp/Computation/Continuations.html#cdr-fstream

The higher-rank type is needed only to express the polymorphic
answertype.