Day / 2014-11-04

by Carsten König

Pascals triangle in Haskell … or why point-free sometimes is pointless

Today I stumpled upon a very nice and concise (but quite hard to understand) point-free implementation of Pascals-Triangle in Haskell:

import Control.Applicative1)<*>

pascal :: [[Int]]
pascal = iterate newrow [1]
  where newrow = (zipWith (+) <*> tail) . (0:) . (++[0])

let’s first confirm that this really works (…magic):

λ> take 5 $ pascal
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Seems to work.

But how …

Of course I know how to get a pascals triangle and I don’t have a problem with iterate.

But the usage of applicative in newrow (together with some doubt about precedence of function application and <*>)
made this very short snippet quite hard to understand for me.

So let’s flesh out newrow out a bit:

newrow = (zipWith (+) <*> tail) . (0:) . (++[0])
==
newrow = 2)zipWith (+ <*> tail) . (0:) . (++ [0])

The last two functions are easy: they just append and prepend a 0 each, so if we look at the types we get:

λ> :t (0:) . (++[0])
(0:) . (++[0]) :: Num a => [a] -> [a]

and we are left with

(zipWith (+)) <*> tail

Now the hard part to understand is what instance of Applicative we are
really using here – and it’s not [] it’s Num a => 3)->) [a])! So the applicative instance are functions taking a list of numbers somewhere. And now of course the types match niecely: λ> :t ...continue -> ([a] -> [a]) -> ([a] -> [a])

So what this really does is taking an row of numbers row, prepends and appends a 0 to it: 0:row++[0].
And then it takes the tail of this and zips the two versions with (+): zipWith (+) (row++[0]) (0:row++[0]).

That’s it.

why not just …

pascal :: [[Int]]
pascal = iterate newrow [1]
  where newrow row = zipWith (+) (0:row) (row++[0])

This is in my opinion easier to read, needs fewer knowledge (don’t need to know about applicatives) and is even shorter!
The only difference is that this does not force point-free style down your throat.

Ok – I cheated a bit (because where is the point in making the list bigger on both sides if zip and tail only uses parts of it anyway).

But I think this is another good case of why sometimes point-free is indeed pointless and should be avoided to make your code more read- and understandable.

Remember: the next person that’s to stupid to understand your clever code is most likely you in 2 months 😀

References   [ + ]

1. ↑ <*>
2. ↑ zipWith (+
3. ↑ ->) [a])!

So the applicative instance are functions taking a list of numbers somewhere.

And now of course the types match niecely:

λ> :t zipWith (+)
zipWith (+) :: Num a => [a] -> ([a] -> [a])

λ> :t tail
tail :: [a] -> [a]

λ> :t (<*>)
(<*>)
  :: Num a => ([a] -> ([a] -> [a]