{-|

Module      : CFold
Description : Continuation passing style, fold
Copyright   : © Frank Jung, 2020
License     : GPL-3

Code from <https://en.wikibooks.org/wiki/Yet_Another_Haskell_Tutorial/Type_basics#Continuation_Passing_Style Yet Another Haskell Tutorial>

-}

module CFold (cfold', cfold) where

-- | CPS fold.
--
-- >>> λ> cfold' (\x t g -> (x : g t)) [] [1..10]
-- [1,2,3,4,5,6,7,8,9,10]
--
-- >>> λ> cfold' (\x t g -> g (x : t)) [] [1..10]
-- [10,9,8,7,6,5,4,3,2,1]
--
cfold' :: (t1 -> t2 -> (t2 -> t2) -> t2) -> t2 -> [t1] -> t2
cfold' :: forall t1 t2. (t1 -> t2 -> (t2 -> t2) -> t2) -> t2 -> [t1] -> t2
cfold' t1 -> t2 -> (t2 -> t2) -> t2
_ t2
z []     = t2
z
cfold' t1 -> t2 -> (t2 -> t2) -> t2
f t2
z (t1
x:[t1]
xs) = t1 -> t2 -> (t2 -> t2) -> t2
f t1
x t2
z (\t2
y -> (t1 -> t2 -> (t2 -> t2) -> t2) -> t2 -> [t1] -> t2
forall t1 t2. (t1 -> t2 -> (t2 -> t2) -> t2) -> t2 -> [t1] -> t2
cfold' t1 -> t2 -> (t2 -> t2) -> t2
f t2
y [t1]
xs)

-- | Wrapper function to `cfold'`.
--
-- >>> λ> cfold (+) 0 [1..3]
-- 6
--
-- >>> λ> cfold (:) [] [1..3]
-- [1,2,3]
--
cfold :: (t1 -> t2 -> t2) -> t2 -> [t1] -> t2
cfold :: forall t1 t2. (t1 -> t2 -> t2) -> t2 -> [t1] -> t2
cfold t1 -> t2 -> t2
f = (t1 -> t2 -> (t2 -> t2) -> t2) -> t2 -> [t1] -> t2
forall t1 t2. (t1 -> t2 -> (t2 -> t2) -> t2) -> t2 -> [t1] -> t2
cfold' (\ t1
x t2
t t2 -> t2
g -> t1 -> t2 -> t2
f t1
x (t2 -> t2
g t2
t))