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 So what this really does is taking an row of numbers That’s it. This is in my opinion easier to read, needs fewer knowledge (don’t need to know about applicatives) and is even shorter! Ok – I cheated a bit (because where is the point in making the list bigger on both sides if 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 So the applicative instance are functions taking a list of numbers somewhere. And now of course the types match niecely: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])
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])
.why not just …
pascal :: [[Int]]
pascal = iterate newrow [1]
where newrow row = zipWith (+) (0:row) (row++[0])
The only difference is that this does not force point-free style down your throat.zip
and tail
only uses parts of it anyway).
1. ↑ <*> 2. ↑ zipWith (+ 3. ↑ ->) [a])!
λ> :t zipWith (+)
zipWith (+) :: Num a => [a] -> ([a] -> [a])
λ> :t tail
tail :: [a] -> [a]
λ> :t (<*>)
(<*>)
:: Num a => ([a] -> ([a] -> [a]