[Haskell-cafe] Re: Lists vs. Monads
jcast at ou.edu
Sun Jul 17 14:49:24 EDT 2005
oleg at pobox.com wrote:
> Jonathan Cast wrote:
> > 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'
> The higher-rank type is needed only to express the polymorphic
OK. Right. I forgot about the Church encoding. Bad jcast, no cookie.
More information about the Haskell-Cafe