Re: Faster break and span for Prelude

27 Dec 2011

      On 27 December 2011 22:40, Bas van Dijk  wrote:
...
However I do expect them to be significantly faster when they are
applied fully saturated.
This looks to be correct when looking at the core of a fully saturated
application:

spanApplied = span (==1) (replicate 1000 1 :: [Int])

You can see that in the generated core the (==1) is passed to the
worker function $wspan:

spanApplied =
  case $wspan@ Int (==1) (replicate 1000 1) of _
    { (# ww1_aoo, ww2_aop #)

$wspan =
  \ (@ a_aa0)
    (w_snj :: a_aa0 -> Bool)
    (w1_snk :: [a_aa0]) ->
    case w1_snk of wild_X9 {
      [] -> (# [] @ a_aa0, [] @ a_aa0 #);
      : x1_aas xs'_aat ->
        case w_snj x1_aas of _ {
          False -> (# [] @ a_aa0, wild_X9 #);
          True ->
            let {
              ds_smn [Dmd=Just D(SS)] :: ([a_aa0], [a_aa0])

              ds_smn =
                case $wspan @ a_aa0 w_snj xs'_aat
                of _ { (# ww1_snO, ww2_snP #) ->
                (ww1_snO, ww2_snP)
                } } in
            (# :
                 @ a_aa0 x1_aas
                     (case ds_smn of _
                        { (ys_Xdu, zs_Xdl) -> ys_Xdu })
            ,
               case ds_smn of _
                 { (ys_ad7, zs_Xdu) -> zs_Xdu }
            #)
        }
    }

While in:

newSpanApplied = newspan (==1) (replicate 1000 1 :: [Int])

the (==1) is "fused" into the worker function $wgo:

newSpanApplied =
  case $wgo (replicate 1000 1)
  of _ { (# ww1_spk, ww2_spl #) -> (ww1_spk, ww2_spl)}

$wgo =
  \ (w_soQ :: [Int]) ->
    case w_soQ of wild_Xb {
      [] ->
        (# [] @ Int, [] @ Int #);
      : x1_abE xs'_abF ->
        case x1_abE of wild1_amK { I# x2_amM ->
        case x2_amM of _ {
          __DEFAULT -> (# [] @ Int, wild_Xb #);
          1 ->
            let {
              ds_snn [Dmd=Just D(SS)] :: ([Int], [Int])

              ds_snn =
                case $wgo xs'_abF of _
		  { (# ww1_spk, ww2_spl #) ->
		    (ww1_spk, ww2_spl)
                  }
		} in
            (# : @ Int
                 wild1_amK
                 ( case ds_snn of _
		     { (ys_Xmv, zs_Xmm) -> ys_Xmv })
            , case ds_snn of _
		     { (ys_am6, zs_Xmv) -> zs_Xmv }
            #)
        }
        }
    }

(BTW I'm using GHC-7.4.1-rc1)

Bas