Data.Foldable.foldr1 too strict

Henning Thielemann

26 Sep 2012 26 Sep '12

6:21 p.m.

I found that the default implementation of foldr1 in Data.Foldable is too strict (and foldl1, too). It always evaluates the complete spine of an input list: -- taken from base-4.6:Data.Foldable.foldr1 foldr2 f xs = fromMaybe (P.error "foldr1: empty structure") (Fold.foldr mf Nothing xs) where mf x Nothing = Just x mf x (Just y) = Just (f x y) -- lazier version, only evaluates one item ahead foldr3 f xs = fromMaybe (P.error "foldr1: empty structure") (Fold.foldr mf Nothing xs) where mf x = Just . maybe x (f x) *Data.NonEmpty> foldr2 (P.++) $ "abc" : "def" : P.undefined "*** Exception: Prelude.undefined *Data.NonEmpty> foldr3 (P.++) $ "abc" : "def" : P.undefined "abc*** Exception: Prelude.undefined

Show replies by date

Brent Yorgey

27 Sep 27 Sep

10:09 a.m.

On Thu, Sep 27, 2012 at 12:21:32AM +0200, Henning Thielemann wrote:

...

I found that the default implementation of foldr1 in Data.Foldable is too strict (and foldl1, too). It always evaluates the complete spine of an input list:

-- taken from base-4.6:Data.Foldable.foldr1 foldr2 f xs = fromMaybe (P.error "foldr1: empty structure") (Fold.foldr mf Nothing xs) where mf x Nothing = Just x mf x (Just y) = Just (f x y)

-- lazier version, only evaluates one item ahead foldr3 f xs = fromMaybe (P.error "foldr1: empty structure") (Fold.foldr mf Nothing xs) where mf x = Just . maybe x (f x)

*Data.NonEmpty> foldr2 (P.++) $ "abc" : "def" : P.undefined "*** Exception: Prelude.undefined

*Data.NonEmpty> foldr3 (P.++) $ "abc" : "def" : P.undefined "abc*** Exception: Prelude.undefined

Isn't that still too strict? I would expect to see "abcdef" before the exception. -Brent

Ross Paterson

10:29 a.m.

On Thu, Sep 27, 2012 at 03:09:07PM +0100, Brent Yorgey wrote:

...

On Thu, Sep 27, 2012 at 12:21:32AM +0200, Henning Thielemann wrote:

...
*Data.NonEmpty> foldr2 (P.++) $ "abc" : "def" : P.undefined "*** Exception: Prelude.undefined

*Data.NonEmpty> foldr3 (P.++) $ "abc" : "def" : P.undefined "abc*** Exception: Prelude.undefined

Isn't that still too strict? I would expect to see "abcdef" before the exception.

No, foldr3 matches what Data.List.foldr1 does: Prelude> foldr1 (++) $ "abc" : "def" : undefined "abc*** Exception: Prelude.undefined It can't decide whether "def":undefined matches [x].

Dan Doel

10:32 a.m.

On Thu, Sep 27, 2012 at 10:09 AM, Brent Yorgey wrote:

...

Isn't that still too strict? I would expect to see "abcdef" before the exception.

No, even foldr1 as hand-written on lists needs to look ahead. Normally it looks like: foldr1 f [x] = x foldr1 f (x:xs) = f x (foldr1 xs) but this is of course sugar for: foldr1 f (x:[]) = x foldr1 f (x:xs) = f x (foldr1 f xs) Where it's more obvious that it will hit the bottom before it can yield the "def". -- Dan

Bertram Felgenhauer

11:36 a.m.

Dan Doel wrote:

...

On Thu, Sep 27, 2012 at 10:09 AM, Brent Yorgey wrote:

...
Isn't that still too strict? I would expect to see "abcdef" before the exception.

No, even foldr1 as hand-written on lists needs to look ahead. Normally it looks like:

foldr1 f [x] = x foldr1 f (x:xs) = f x (foldr1 xs)

[...]

...

Where it's [more] obvious that it will hit the bottom before it can yield the "def".

But we could define foldr1 f (x:xs) = foldr f x xs which would be more lazy. I see no advantage to defining foldr1 as in the standard library, am I missing anything? Bertram

Ian Lynagh

12:06 p.m.

On Thu, Sep 27, 2012 at 05:36:00PM +0200, Bertram Felgenhauer wrote:

...

But we could define

foldr1 f (x:xs) = foldr f x xs

which would be more lazy. I see no advantage to defining foldr1 as in the standard library, am I missing anything?

That doesn't have the right behaviour: Prelude> Data.List.foldr1 (-) [3,5] -2 Prelude> let foldr1 f (x:xs) = foldr f x xs in foldr1 (-) [3,5] 2 Thanks Ian

4620

Age (days ago)

4621

Last active (days ago)

List overview

Download

5 comments

6 participants

participants (6)

Bertram Felgenhauer
Brent Yorgey
Dan Doel
Henning Thielemann
Ian Lynagh
Ross Paterson