polymorphism and lists (was Re: Two prelude/library matters)

[S. Alexander Jacobson]

On Fri, 6 Nov 1998, Simon Peyton-Jones wrote:
> I have three small (and late) prelude/library proposals to add:
> 1.  The Show class
> ~~~~~~~~~~~~~~~~~~
>       * Add 'show' as a class method of class Show, to give:
> This breaks nothing (show has the same type as before), but it allows
> someone to say
>               instance Show T where
>                  show x = ...
> to make T an instance of Show.   


If changes like this are legitimate at this stage, can we do something
similar for other functions in the Prelude as well. 
Separate from the issue of using the names in the prelude for other things
(homonyms), is the issue of using names in the prelude for the same
operation on different datastructures.  
E.g. in the list prelude, sum product maximum and minimum are all
functions that can apply to a tree just as easily as they can apply to a
list.  It would be nice to allow the user to define 

> instance HasSum Tree where
>  sum t = ....

My real opinion here is that users shouldn't have to declare the instance
explicitly for single function classes; e.g. the user could do:

> sum t = treeFold (+) t

but that probably goes beyond H98.
---
On a slightly different front, naive use of the existing list
implementation can be very inefficient (see the discussion of quicksort
from a while back). 

The prelude has the function cycle in which the time it takes to get the
next item in the resulting list grows quadratically, I think:

cycle xs         =  xs' where xs' = xs ++ xs'

A solution to this problem would be to allow the user to define
alternative list implementations which could more efficiently deal with
++.  The existing prelude list functions prevent this solution.
For example, suppose I want to use my own list datastructure:

> data MyList a = Nil | Cons a List | Cat MyList MyList

I would like to use the list functions defined in the Prelude on my new
data structure, but I can't (both because I can't use their names) and
because many of the implementations rely on pattern matching rather than a
standard list interface like foldr and foldl.

My suggestion (based on one of Erik's papers) is that 
1. the Prelude should define a list class like:
> class List a where
>  foldr            :: (a -> b -> b) -> b -> [a] -> b
>  foldl            :: (a -> b -> a) -> a -> [b] -> a
> ...--default implentations of head, tail, last, ++

2. the prelude list functions should be converted to use foldr and foldl

With these changes users can apply all the prelude list functions to their
favorite datastructures and implement more optimized versions of certain
functions when appropriate.


___________________________________________________________________
S. Alexander Jacobson                   i2x Media  
1-212-697-0184 voice                    1-212-697-1427 fax