Henning Thielemann | 27 Sep 00:21 2012
Picon

Data.Foldable.foldr1 too strict


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
Brent Yorgey | 27 Sep 16:09 2012

Re: Data.Foldable.foldr1 too strict

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 | 27 Sep 16:29 2012
Picon

Re: Data.Foldable.foldr1 too strict

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 | 27 Sep 16:32 2012
Picon

Re: Data.Foldable.foldr1 too strict

On Thu, Sep 27, 2012 at 10:09 AM, Brent Yorgey <byorgey <at> seas.upenn.edu> 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 | 27 Sep 17:36 2012

Re: Data.Foldable.foldr1 too strict

Dan Doel wrote:
> On Thu, Sep 27, 2012 at 10:09 AM, Brent Yorgey <byorgey <at> seas.upenn.edu> 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 | 27 Sep 18:06 2012
Picon

Re: Data.Foldable.foldr1 too strict

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

Gmane