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