第40回　Stream Fusionによる融合変換で処理系の最適化機能を生かす

-- Data.List.Stream モジュールでの定義
filter :: (a -> Bool) -> [a] -> [a]

～ 略 ～

{-# NOINLINE [1] filter #-}
{-# RULES
"filter -> fusible" [~1] forall f xs.
    filter f xs = unstream (Stream.filter f (stream xs))
--"filter -> unfused" [1] forall f xs.
--    unstream (Stream.filter f (stream xs)) = filter f xs
  #-}

filter :: (a -> Bool) -> Stream a -> Stream a
filter p (Stream next0 s0) = Stream next s0
  where
    {-# INLINE next #-}
    next !s = case next0 s of
      Done                   -> Done
      Skip    s'             -> Skip    s'
      Yield x s' | p x       -> Yield x s'
                 | otherwise -> next    s'

data Step a s = Yield a !s
              | Skip    !s
              | Done

-- 実際の Data.Stream モジュールでの定義
filter :: (a -> Bool) -> Stream a -> Stream a
filter p (Stream next0 s0) = Stream next s0
  where
    {-# INLINE next #-}
    next !s = case next0 s of
      Done                   -> Done
      Skip    s'             -> Skip    s'
      Yield x s' | p x       -> Yield x s'
                 | otherwise -> Skip    s'
{-# INLINE [0] filter #-}

{-# RULES
    "Stream filter/filter fusion" forall p q s.
        filter p (filter q s) = filter (\x -> q x && p x) s
 #-}

unstream :: Stream a -> [a]
unstream (Stream next s0) = unfold_unstream s0
  where
    unfold_unstream !s = case next s of
      Done       -> []
      Skip    s' -> expose s' $     unfold_unstream s'
      Yield x s' -> expose s' $ x : unfold_unstream s'

sum :: Num a => Stream a -> a
sum (Stream next s0) = loop_sum 0 s0
  where
    loop_sum !a !s = case next s of   -- note: strict in the accumulator!
      Done       -> a
      Skip    s' -> expose s' $ loop_sum a s'
      Yield x s' -> expose s' $ loop_sum (a + x) s'