Re: [GHC] #14387: listToMaybe doesn't participate in foldr/build fusion

25 Oct 2017

      #14387: listToMaybe doesn't participate in foldr/build fusion
-------------------------------------+-------------------------------------
        Reporter:  duog              |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Core Libraries    |              Version:  8.2.1
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):
...
findIndex{2,4,5} get join points and findIndex{"",3} don't.
Actually `findIndex3` does get a join point:
 {{{
 FindIndex.findIndex3
   = \ (@ a_a1kV)
       (p_s2Z2 [Occ=OnceL!] :: a_a1kV -> GHC.Types.Bool)
       (eta_s2Z3 [Occ=Once] :: [a_a1kV]) ->
       case GHC.List.zip
              @ GHC.Types.Int @ a_a1kV FindIndex.findIndex1 eta_s2Z3
       of sat_s2Zd
       { __DEFAULT ->
       joinrec {
         go_s2Z4 [Occ=LoopBreakerT[1]]
           :: [(GHC.Types.Int, a_a1kV)] -> GHC.Base.Maybe GHC.Types.Int
         [LclId[JoinId(1)], Arity=1, Str=, Unf=OtherCon []]
         go_s2Z4 (ds_s2Z5 [Occ=Once!] :: [(GHC.Types.Int, a_a1kV)])
           = case ds_s2Z5 of {
               [] -> GHC.Base.Nothing @ GHC.Types.Int;
               : ds1_s2Z7 [Occ=Once!] xs_s2Z8 [Occ=Once] ->
                 case ds1_s2Z7 of { (i_s2Za [Occ=Once], x_s2Zb [Occ=Once])
 ->
                 case p_s2Z2 x_s2Zb of {
                   GHC.Types.False -> jump go_s2Z4 xs_s2Z8;
                   GHC.Types.True -> GHC.Base.Just @ GHC.Types.Int i_s2Za
                 }
                 }
             }; } in
       jump go_s2Z4 sat_s2Zd
       }
 }}}
 Note the join point.  But `findIndex4` and `findIndex` do not.  Maybe that
 was a typo.
...
Having a join point means constant stack space, not having a join point
 means linear stack space.
This definitely isn't true.  Here's `findIndex` (the one that does not get
 a join point):
 {{{
 findIndex
   = \ (@ a_a1IQ) (p_a1eN :: a_a1IQ -> Bool) (x_a1Ld :: [a_a1IQ]) ->
       letrec {
         go_a1KZ [Occ=LoopBreaker] :: [a_a1IQ] -> Int# -> [Int]
         [LclId, Arity=2, Str=, Unf=OtherCon []]
         go_a1KZ
           = \ (ds_a1L0 :: [a_a1IQ]) (eta_B1 :: Int#) ->
               case ds_a1L0 of {
                 [] -> GHC.Types.[] @ Int;
                 : y_a1L5 ys_a1L6 ->
                   case p_a1eN y_a1L5 of {
                     False -> go_a1KZ ys_a1L6 (+# eta_B1 1#);
                     True ->
                       GHC.Types.:
                         @ Int (GHC.Types.I# eta_B1) (go_a1KZ ys_a1L6 (+#
 eta_B1 1#))
                   }
               }; } in
       case go_a1KZ x_a1Ld 0# of {
         [] -> GHC.Base.Nothing @ Int;
         : a1_aX7 ds_d1KM -> GHC.Base.Just @ Int a1_aX7
       }
 }}}
 In the `False` branch inside `go`, there's a tail-call to `go` (no stack
 growth). In the `True` branch, `go` returns a cons-cell, and stops.  Then
 the `case go x o# of ...` scrutinises that cons cell and returns a `Just`.
 All done. No stack growth in either case.

 Why does `listToMaybe'` work (slightly) better?  Because it can perform
 foldr/build fusion with the list producer.
...
it seems that changing the definition of listToMaybe to use `foldr`
 would be a win
Yes I agree.  It's a bit like making `map` use `foldr` rather than being
 written directly.  But you'd need an INLINE pragma on it.

 I can't see a downside.  If it doesn't fuse you get the original
 `listToMaybe` back instead.   If someone makes that change (in `base`) do
 add a Note to explain.

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