darcs patch: Make toList a member of Foldable
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). In other words, any code that directly or indirectly uses Foldable's toList on values of these types needlessly performs O(n) conversions where O(1) conversions are available. Fortunately, the solution is very simple: just make toList a member of the Foldable type class. I have attached a patch that does just this.
Dear Eelis,
Fortunately, the solution is very simple: just make toList a member of the Foldable type class.
I have attached a patch that does just this.
Thanks! We have a procedure for library contributions. See http://www.haskell.org/haskellwiki/Library_submissions to find out what steps to take in order to get your patch pushed. All the best, Stefan
On 2010-04-27 19:00, Stefan Holdermans wrote:
See [Library_submissions] to find out what steps to take in order to get your patch pushed.
Thanks Stefan, I have filed a corresponding Trac ticket: http://hackage.haskell.org/trac/ghc/ticket/4024 The guidelines also mention specifying a "timescale for consideration", but I'm not sure what that means. Naively I'd simply expect "as long as it takes"; I don't really feel entitled to set deadlines for other volunteers.. :)
Eelis,
The guidelines also mention specifying a "timescale for consideration", but I'm not sure what that means. Naively I'd simply expect "as long as it takes"; I don't really feel entitled to set deadlines for other volunteers.. :)
Typically, two weeks or so is fine. Cheers, Stefan
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
On 2010-04-27 23:22, Isaac Dupree wrote:
Can this be implemented in terms of GHC's RULES?
Hi Isaac, Thanks a lot for mentioning the RULES pragma, which I did not know about. It turns out that using it to specialize Foldable's toList for things like NonEmptyList works like a charm. Indeed, this is exactly the use case described in: http://www.haskell.org/ghc/docs/latest/html/users_guide/rewrite-rules.html#r... Hence, there's no need to make toList a member of Foldable (which, as you rightly point out, has other problems), and so I withdraw my proposal. :) Sorry for the noise, Eelis
On Tue, Apr 27, 2010 at 11:53:47PM +0200, Eelis van der Weegen wrote:
Thanks a lot for mentioning the RULES pragma, which I did not know about. It turns out that using it to specialize Foldable's toList for things like NonEmptyList works like a charm.
If the existing rules don't already do this for [], it needs fixing. The instance for NonEmpty should be instance Foldable NonEmpty where foldr f x (NonEmpty h t) = f h (foldr f x t) which would then rely on the optimization of the [] instance.
On 2010-04-28 00:37, Ross Paterson wrote:
The instance for NonEmpty should be
instance Foldable NonEmpty where foldr f x (NonEmpty h t) = f h (foldr f x t)
which would then rely on the optimization of the [] instance.
Even with such an optimal foldr, the generic toList would still reconstruct the whole list, which would still be O(n) instead of O(1), no?
On Wed, Apr 28, 2010 at 12:53:27AM +0200, Eelis van der Weegen wrote:
Even with such an optimal foldr, the generic toList would still reconstruct the whole list, which would still be O(n) instead of O(1), no?
The definition in Data.Foldable is toList :: Foldable t => t a -> [a] toList t = build (\ c n -> foldr c n t) For lists, this Data.Foldable.foldr should be inlined to Data.List.foldr. (Hmm, does the INLINE of toList block that?) If this build isn't eliminated by some outer foldr, it should eventually unfold its definition: build g = g (:) [] giving toList t = foldr (:) [] t and the rule "foldr/id" should reduce that to toList t = t If this isn't happening, it needs fixing.
On Wed, Apr 28, 2010 at 12:21:58AM +0100, Ross Paterson wrote:
On Wed, Apr 28, 2010 at 12:53:27AM +0200, Eelis van der Weegen wrote:
Even with such an optimal foldr, the generic toList would still reconstruct the whole list, which would still be O(n) instead of O(1), no?
The definition in Data.Foldable is
toList :: Foldable t => t a -> [a] toList t = build (\ c n -> foldr c n t)
For lists, this Data.Foldable.foldr should be inlined to Data.List.foldr.
For NonEmptyList this should become toList t = build (\ c n -> c h (Data.List.foldr c n t)) I'd expect the rest of the steps to still apply, but these RULES are tricky.
On 2010-04-28 01:30, Ross Paterson wrote:
On Wed, Apr 28, 2010 at 12:21:58AM +0100, Ross Paterson wrote:
The definition in Data.Foldable is
toList :: Foldable t => t a -> [a] toList t = build (\ c n -> foldr c n t)
For lists, this Data.Foldable.foldr should be inlined to Data.List.foldr.
For NonEmptyList this should become
toList t = build (\ c n -> c h (Data.List.foldr c n t))
I'd expect the rest of the steps to still apply, but these RULES are tricky.
I checked, and with your version of foldr for NonEmptyList, it does seem to work beautifully, so that's fantastic! Thank you for the explanation and solution. I'll ask the maintainer of the NonEmptyList package to use this version.
participants (4)
-
Eelis van der Weegen -
Isaac Dupree -
Ross Paterson -
Stefan Holdermans