darcs patch: Make toList a member of Foldable

[Isaac Dupree]

On 04/27/10 11:12, Eelis van der Weegen wrote:
> The toList function in Data.Foldable is currently not a member of the
> Foldable type class, and is consequently not specializable.
>
> This is a great shame, because for data types such as [a] and
>
>    data NonEmptyList a = NonEmptyList a [a]
>
> conversion to list can trivially be implemented in O(1) instead of the
> generic toList's O(n).

Can this be implemented in terms of GHC's RULES?  For example,

data NonEmptyList a = NonEmptyList a [a]
instance Foldable NonEmptyList where {...}
{-# RULES "NonEmptyList/toList" toList = nonEmptyListToList #-}
nonEmptyListToList :: NonEmptyList a -> [a]
nonEmptyListToList (NonEmptyList a as) = a : as

(does that work? The reason it has a chance to work is that RULES are 
only applied when they are type-correct; I haven't used them enough 
myself to know how to test them though.)

Now, in the past, we've frowned on using RULES to improve asymptotic 
complexity.

Contrarily,
- In many cases this RULE will not affect the complexity because there's 
often a parallel O(n) operation.
- 'Foldable' is not actually specific to lists... if you want to put a 
'toList' operation into the class because it can make the operation 
O(1), how do we argue against a hypothetical toSequence or toVector 
operation in the class (in case an instance of Foldable contained a 
Data.Sequence somewhere - then we could make its toSequence be O(1)!) 
(RULES can treat all these types equally already...)

-Isaac