{-# LANGUAGE ScopedTypeVariables, PatternSynonyms #-}
module SumTreeToList (foo1, foo2, foo1_noOS, foo2_noOS, manual) where

import GHC.Exts hiding (toList)

data Tree = Tip Int | Bin Tree Tree

toList :: Tree -> [Int]
toList tree = build (toListFB tree)
{-# INLINE toList #-}

toListFB :: Tree -> (Int -> r -> r) -> r -> r
toListFB root cons nil = go root nil
  where
    go (Tip x) rest = cons x rest
    go (Bin x y) rest = go x (go y rest)
{-# INLINE toListFB #-}

toList' :: Tree -> [Int]
toList' tree = build (toListFB' tree)
{-# INLINE toList' #-}

toListFB' :: Tree -> (Int -> r -> r) -> r -> r
toListFB' root cons nil = go root []
  where
    go (Tip x) s = cons x (goS s)
    go (Bin x y) s = go x (y:s)
    goS [] = nil
    goS (x:xs) = go x xs
{-# INLINE toListFB' #-}

f :: Int -> Bool
f x = True
{-# NOINLINE f #-}

foo1 :: Tree -> Int
foo1 t = sum (filter f (toList t))

foo2 :: Tree -> Int
foo2 t = sum (filter f (toList' t))

foo1_noOS :: Tree -> Int
foo1_noOS t = sum_noOS (filter f (toList t))

foo2_noOS :: Tree -> Int
foo2_noOS t = sum_noOS (filter f (toList' t))

foldl'_noOS           :: forall a b . (b -> a -> b) -> b -> [a] -> b
{-# INLINE foldl'_noOS #-}
foldl'_noOS k z0 xs =
  foldr (\(v::a) (fn::b->b) (z::b) -> z `seq` fn (k z v)) (id :: b -> b) xs z0

sum_noOS = foldl'_noOS (+) 0


manual :: Tree -> Int
manual t = go t 0
  where
    go (Tip x) a = if f x then a + x else a
    go (Bin l r) a = go l (go r a)