Re: [GHC] #9742: The default definitions of foldl1 and foldr1 are too strict

29 Oct 2014

      #9742: The default definitions of foldl1 and foldr1 are too strict
-------------------------------------+-------------------------------------
              Reporter:  dfeuer      |            Owner:  ekmett
                  Type:  bug         |           Status:  new
              Priority:  normal      |        Milestone:  7.10.1
             Component:  Core        |          Version:  7.9
  Libraries                          |         Keywords:
            Resolution:              |     Architecture:  Unknown/Multiple
      Operating System:              |       Difficulty:  Easy (less than 1
  Unknown/Multiple                   |  hour)
       Type of failure:  Runtime     |       Blocked By:
  crash                              |  Related Tickets:
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------
Description changed by dfeuer:

Old description:
...
We currently have
{{{#!hs
    foldr1 :: (a -> a -> a) -> t a -> a
    foldr1 f xs = fromMaybe (error "foldr1: empty structure")
                    (foldr mf Nothing xs)
      where
        mf x Nothing = Just x
        mf x (Just y) = Just (f x y)
}}}
This has to traverse the entire list before it can do anything. What we
want is
{{{#!hs
mf x r = Just $ case r of
                  Nothing -> x
                  Just y -> f x y
}}}
New description:

 We currently have

 {{{#!hs
     foldr1 :: (a -> a -> a) -> t a -> a
     foldr1 f xs = fromMaybe (error "foldr1: empty structure")
                     (foldr mf Nothing xs)
       where
         mf x Nothing = Just x
         mf x (Just y) = Just (f x y)
 }}}

 This has to traverse the entire container before it can do anything. What
 we want is

 {{{#!hs
         mf x r = Just $ case r of
                           Nothing -> x
                           Just y -> f x y
 }}}

--

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9742#comment:1
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler