There and Back Again

taba.hs

--  There and Back Again
--  http://www.brics.dk/RS/02/12/BRICS-RS-02-12.pdf

--  Fold a function over a sequence and the reverse of another sequence, in
--  just one passage.
taba :: ((t1, t2) -> t -> t) -> t -> [t1] -> [t2] -> t
taba f b xs ys =
        let (r, _) = foldr (\x (r, y:ys) -> (f (x,y) r, ys))
                    (b, ys)
                    xs
        in r

--  Memory-less taba: each result of the intermediate accumulator does not
--  depend on previous results.
taba' :: (t1 -> t2 -> t3) -> (t3 -> t -> t) -> t -> [t1] -> [t2] -> t
taba' f1 f2 = taba (\(x, y) acc -> f2 (f1 x y) acc)

--  Memory-less self-taba: fold a sequence over itself.
taba'' :: (t2 -> t2 -> t3) -> (t3 -> t -> t) -> t -> [t2] -> t
taba'' f1 f2 b xs = taba' f1 f2 b xs xs

--  Examples

--  Simple accumulator
acc :: [t1] -> [t2] -> [(t1, t2)]
acc = taba (:) []

--  Convolution
conv :: Num a => [a] -> [a] -> [a]
conv = taba' (+) (:) []

--  Palindrome
isPalindrome :: Eq t2 => [t2] -> Bool
isPalindrome = taba'' (==) (&&) True

--  Catalan numbers
--  http://en.wikipedia.org/wiki/Catalan_number
catalan :: Integer -> Integer
catalan 0 = 1
catalan n = taba'' (*) (+) 0 (map catalan [0..n - 1])