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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe