jump to navigation

TABA pattern in Haskell June 6, 2009

Posted by haskelladdict in Haskell.
Tags: , , , ,
add a comment

After a recent discussion on Haskell-Cafe I read over the excellent paper entitled There and Back Again (TABA) by Danvy and Goldberg and was quite fascinated.

So what is TABA? In a nutshell, the TABA pattern utilizes a recursive function to traverse a data structure such as a list at return time. This allows one to, e.g.,  convolve two list [x1, x2, …, xn] and [y1, y2, …, yn] to yield

[(x1,yn), (x2,yn-1), …, (xn,y1)]

in only n recursive calls.

So how does this work? The main idea is that during the recursive traversal of the first list we build up a stack of functions each of which is responsible for generating one of the final list elements. During stack unwinding these function are being replayed and generate the final result. The authors of the TABA paper liken it to winding a spring during the recursive traversal. If this sounds a bit too abstract here’s a Haskell implementation of a list convolution function using the TABA pattern

>convolve :: [a] -> [b] -> [(a,b)]
>convolve xs ys = fst . walk $ xs
>  where
>    walk []        = ([],ys)
>    walk (a:as) = let
>                            (r, (b:bs)) = walk as
>                          in
>                            ((a,b):r, bs)

Isn’t that great!? Even better, the above can nicely be written as a fold like so

>convolve1 :: [a] -> [b] -> [(a,b)]
>convolve1 xs ys = fst . foldr (\x (r,(a:as)) -> ((x,a):r,as)) ([],ys) $ xs

If this has whet your appetite please consult the TABA paper for a much better and more in depth exposition. Enjoy!