Pascal's Triangle

Pascal's triangle can be defined directly

> pascal1 0 _ = 1
> pascal1 _ 0 = 1
> pascal1 n m = pascal1 (n-1) m + pascal1 n (m-1)

This direct implementation is very inefficient, much as the direct computation of the Fibonacci sequence

> fib 0 = 0
> fib 1 = 1
> fib n = fib (n-1) + fib (n-2)

is inefficient. An elegant way to compute this sequence exploits sharing and laziness.

> fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

So, for example, fib 6 == fibs!!6. (You can see the above defintion and others on the Haskell wiki.) A nice exercise is to pull the same stunt with Pascal's triangle. Instead of a list we need a tree and some obvious operations on it.

> data T a = T a (T a) (T a)
> 
> left :: T a -> T a
> left (T _ l _) = l
> 
> right :: T a -> T a
> right (T _ _ r) = r
> 
> value :: T a -> a
> value (T x _ _) = x
> 
> zipTreeWith :: (a -> b -> c) -> T a -> T b -> T c
> zipTreeWith op (T x1 l1 r1) (T x2 l2 r2) =
>       T (op x1 x2) (zipTreeWith op l1 l2) (zipTreeWith op r1 r2)

We can now define a generic (replacing addition with an arbitrary operation op) Pascal's triangle.

> pascals' :: a -> (a -> a -> a) -> T a
> pascals' i op = T i l r
>    where m = zipTreeWith op l r
>          l = leftone m
>          r = rightone m
>          leftone t = T i (leftone (left t)) t
>          rightone t = T i t (rightone (right t))

(The above version is due to JS and I prefer it to the version I came up with.) We get what we want by specialising.

> pascals :: T Integer
> pascals = pascals' 1 (+)

We make it easy to get values out of the tree with this helper:

> pascalsHelper n m = value $ (iterate right ((iterate left pascals)!!n))!!m

Finally we can test it.

> main = print $ and [pascalsHelper x y == pascal1 x y| x <- [1..5], y <- [1..5]]

Formatting Haskell

I've been experimenting with formatting Haskell for this blog and thought I would summarize my conclusions.

My needs are unsurprising: I want to write literate Haskell (LHS), have it look nice on the blog, and have the process be easy (in other words, mostly automated).

One possibility is to take the LHS, wrap it in <pre> tags and post it. This works, but I was curious to try hscolour. The current version (I got mine directly from darcs) supports LHS. A nice feature of hscolour is that it can output HTML with the formatting in the form CSS classes. Thus, I could factor out the appearance of my Haskell code into the embedded stylesheet of my blog template.

This left me with just one minor quibble. I wanted to hide the "> " with which every line of code in LHS starts. Unfortunately the current implementation of hscolor treats these as a regular Haskell token, so they get styled like any other operator. So after a little hacking of the hscolour source, I had a new hscolour that did exactly what I wanted.

The color scheme is nothing to write home about, but while tinkering with it I did discover a small quirk of how browsers interpret CSS (it might not even be a quirk -- I should read the W3C spec). I wanted to style "> " with display:none. However with that property, if you cut and paste the post, you lose the "> "s. So instead I just made them the same color as the backgound.

Finally I used an OMake script to automate compiling the code and converting it into HTML.

If I had a great deal of spare time, the following would be nice.

• Integrate Pandoc into the process so my LHS can look more like text and yet be mechanically converted to pleasant HTML.
• Automate the upload process using the blog's XML API. Others have already done something similar.

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.

Are partial functions null in sheep's clothing? For example > length [1,2,undefined] is 3, but what is the third (!!2) element? Kind of like inserting null into a list.

The Inevitable First Post

My first post.

A block quote with two lines

Also, here is some code with a printf

void main() {
  printf("hello");
}

So there. This should not be on a new line. Nor should this.
This should be on a new line.

And this should be two lines down.