Language extension idea (was Re: [Haskell-cafe] Re: OCaml list sees...)

[oleg at pobox.com]

Tom Pledger wrote:

> Something along these lines:
>
>     class List l a | l -> a where
>         nil :: l
>         cons :: a -> l -> l
>
> But that's not of much use, because there isn't a class method to
> recover the elements of a List. We could add more methods (corresponding
> to null, head, and tail)

Actually we merely need to add a deconstructor. Also, we can leave the
type of elements fully polymorphic. Something like this:

> class List l where
>     nil :: l a
>     cons :: a -> l a -> l a
>     decon :: l a
> 	     -> w -- on empty
> 	     -> (a -> l a -> w)
> 	     -> w
>
> instance List [] where
>     nil = []
>     cons = (:)
>     decon [] on_nil on_cons = on_nil
>     decon (h:t) on_nil on_cons = on_cons h t

we can then write truly generic list-processing functions:

> rev:: List l => l a -> l a
> rev l = rev' l nil
>  where
>    rev' l acc = decon l acc (\h t -> rev' t (cons h acc))

not in a terribly convenient way though.

   *Foo> rev "abc"
   "cba"