Re: [GHC] #876: Length is not a good consumer

12 Feb 2013

      #876: Length is not a good consumer
--------------------------------------+-------------------------------------
  Reporter:  ariep@…                  |          Owner:                  
      Type:  bug                      |         Status:  new             
  Priority:  lowest                   |      Milestone:  7.6.2           
 Component:  libraries/base           |        Version:  6.5             
Resolution:                           |       Keywords:  length          
        Os:  Linux                    |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug  |     Difficulty:  Unknown         
  Testcase:  list003                  |      Blockedby:                  
  Blocking:                           |        Related:                  
--------------------------------------+-------------------------------------

Comment(by simonpj):

 OK, so the problem in Ian's comment 6 years ago (ha ha!) was that the
 naive version of `length` using `foldr` does not lead to a tail recursive
 function.  But after a little reflection I realise that what we want is
 `foldl` with a strict accumulating parameter; and that can be expressed
 using `foldr`. So here is a version that does work (notice the strict
 apply) in `incL`:
 {{{
 len :: [a] -> Int
 len xs = foldr incL id xs 0

 incL :: a -> (Int -> Int) -> Int -> Int
 incL = \_ g x -> g $! (x+1)
 }}}
 To demonstrate:
 {{{
 foo :: Int -> Int -> Int
 foo p q = len [p..q]
 }}}
 Compile with -O to get this nice tight code
 {{{
 Len.$wfoo :: GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int#
 Len.$wfoo =
   \ (ww_sgn :: GHC.Prim.Int#) (ww1_sgr :: GHC.Prim.Int#) ->
     case GHC.Prim.># ww_sgn ww1_sgr of _ {
       GHC.Types.False ->
         letrec {
           $wgo_sgA [Occ=LoopBreaker]
             :: GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int#
           [LclId, Arity=2, Str=DmdType LL]
           $wgo_sgA =
             \ (w_sga :: GHC.Prim.Int#) (ww2_sgd :: GHC.Prim.Int#) ->
               case GHC.Prim.==# w_sga ww1_sgr of _ {
                 GHC.Types.False ->
                   $wgo_sgA (GHC.Prim.+# w_sga 1) (GHC.Prim.+# ww2_sgd 1);
                 GHC.Types.True -> GHC.Prim.+# ww2_sgd 1
               }; } in
         $wgo_sgA ww_sgn 0;
       GHC.Types.True -> 0
     }
 }}}
 So I think we can do this for length in the library.  I need a clean nofib
 run to test, though.

 Simon

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