Is there already a list class?

[David Roundy]

On Wed, Jan 10, 2007 at 02:52:52AM +0100, Marc Weber wrote:
> Is here the right place to request a list class?
> eg
> class List l e where
> 	(:) :: e -> l e -> l e
> 	head :: ..
> 
> This might be used in Data.Set, Data.Map
> 
> class StorableAsList l e t where
> 	fromList :: l e ->  t
> 	toList :: t -> l e
> 
> I'd like to help implementing/ writing it.
> 
> Do you consider this beeing a useful enhancement?

This is a major part of my wishlist for a new set of libraries in the
post-Haskell' era (or perhaps for Haskell').  Rewriting the prelude (which
is essentially what you're suggesting) and standard libraries is part of
the haskell' effort, and most people I have talked with would prefer to
reduce its size as far as possible.

Alas, I don't forsee having any time for this in the forseeable future, but
I've got lots of ideas.

I think you'd want a higher-kinded list type rather than a MPTC:

class List l where
     cons :: e -> l e -> l e -- you can't make a constructor a member of a class
     head :: l e -> e
     null :: l e -> Bool
     empty :: l e
     ...

Also on the wishlist would be to rename fmap to map, and add an instance

instance List l => Functor l where
   map :: (a -> b) -> l a -> l b
   map f l | null l = empty
           | otherwise = f (head l) `cons` tail l

Ideally, I'd like the prelude contain almost no functions that are not
defined within a class, so that we could apply all the standard prelude
functions to any reasonable data type we wish.

In my opinion, the API provided by modules like Data.Map and
Data.FastPackedString which we are forced to import qualified because they
conflict with the Prelude are an abomination forced upon us by the
short-sighted design of the Prelude.  The only argument for not putting
these functions into classes is that it would make error messages harder
for students.  There have been multiple suggestions for alleviating that,
ranging from better compiler error messages (pretty hard) to a special
"easy" prelude.  The latter seems like a better idea.

There are some difficulties, however, such as the trickiness that some data
structures (which you'd like to use the same interface) have constraints,
such as they require that the stored type be in class Ord.  These issues
are a real pain, and I know other people have thought long and hard about
it, but I haven't.
-- 
David Roundy
Department of Physics
Oregon State University