Skip to content

Instantly share code, notes, and snippets.

@lbolla
Created January 15, 2012 17:46
Show Gist options
  • Save lbolla/1616560 to your computer and use it in GitHub Desktop.
Save lbolla/1616560 to your computer and use it in GitHub Desktop.
There and Back Again
-- 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])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment