Saturday, August 25, 2007

Relative Spreadsheets

A post of sigfpe discusses spreadheets (and much more). He defines a beautiful function loeb:
> loeb :: Functor a => a (a x -> x) -> a x
> loeb x = fmap (\a -> a (loeb x)) x
which allows one to define something similar to a (one dimensional) spreadsheet
> spreadsheet1 = [length,\x -> x!!0]
so loeb spreadsheet1 is [2,2]. It can be made more compelling with help of some sugar that makes functions into things we can add and subtract:
> instance Show (x -> a)
> instance Eq (x -> a)
> instance (Num a,Eq a) => Num (x -> a) where
>     fromInteger = const . fromInteger
>     f + g = \x -> f x + g x
>     f * g = \x -> f x * g x
>     negate = (negate .)
>     abs = (abs .)
>     signum = (signum .)
then we can define a more interesting spreadsheet:
> spreadsheet2 = [ (!!5), 3, (!!0)+(!!1), (!!2)*2, sum . take 3, 17]
and loeb spreadsheet2 is [17,3,20,40,40,17]. However the functions living in each cell are absolute. If it were Excel, they would have dollar signs in them. Normal functions in a spreadsheet are best consider to be using relative addressing (this observation is due to JS). At this point you should read the second inspiration for this post, again by sigfpe where he discusses comonads and zippers. Repeating his definitions here, we make U into the zipper derived from a list and define functions to walk left and right along the list. We also make it into a functor.
> data U x = U [x] x [x]
> right (U a b (c:cs)) = U (b:a) c cs
> left  (U (a:as) b c) = U as a (b:c)
> instance Functor U where
>    fmap f (U a b c) = U (map f a) (f b) (map f c)
It turns out that U is a comonad, but all we'll ignore that and simply define the following two oddly-named functions.
> cojoin a = U (tail $ iterate left a) a (tail $ iterate right a)
> coreturn (U _ b _) = b
Next we define a function to walk an integer number of steps along the zipper and a one to access the nth element.
> shift i u = (iterate (if i<0 then left else right) u) !! abs i
> at i u = coreturn (shift i u)
Armed with all this we can define a new loeb function, similar to sigfpe's except that it works in a relative way (which is interesting) but is much less general, since it only works with U.
> uzipWith :: (a -> b -> c) -> U a -> U b -> U c
> uzipWith op (U laa a raa) (U lbb b rbb) = U (zipWith op laa lbb) (op a b) (zipWith op raa rbb)
> uloeb :: U (U x -> x) -> U x
> uloeb ff = uzipWith ($) ff (cojoin (uloeb ff))
Finally we can define our Fibonacci spreadsheet.
> fibSpreadsheet = U (repeat 0) 1 (repeat (at (-1) + at (-2)))
(At this point it's hard not to think of The Evolution of a Haskell Programmer.) Now to test it, we define an obviously correct (and inefficient) computation of the Fibonacci sequence.
> fib 0 = 1
> fib 1 = 1
> fib n = fib (n-1) + fib (n-2)
> main = do let U _ _ rr = uloeb fibSpreadsheet
>           print $ map fib [1..10] == take 10 rr
Two parting comments:
  • uloeb fibSpreadsheet is, in fact, efficient.
  • The definition of cojoin could have used repeat instead of iterate left and iterate right, in which case uloeb would have ended up being an absolute version of this one, i.e., it would have similar to sigfpe's loeb except not as general.
  • uloeb is not as general as I might have hoped. It would be nice if it worked with any functor, or perhaps comonad. Perhaps there is some other type class lurking here.

1 comment:

sigfpe said...

Not just relative spreadsheets, infinite in both directions relative spreadsheets! :-)