## 2011年7月13日水曜日

The fifth trial of implementing a classic algorithm with Haskell!
Today I'll try Pascal' Triangle.
`pascalTriangle x = x : pascalTriangle y             where y = zipWith (+) (0:x) (x++[0])`
Nothing special. Thanks to lazy evaluation, you can define an infinite list of Pascal's Triangle.

Here's a similar problem:
Let's consider how many times it lands heads if you toss a coin. More specifically, what the probability of the coin landing heads k times out of n tosses?

It seems it's nothing to do with Pascal's Triangle. But it actually is.
`prbTree x = x : prbTree y       where y = zipWith (+) (map (*0.5) (0:x)) (map (*0.5) (x++[0]))`
The tree structure is just like Pascal's Triangle.
In the above source, I used floating point numbers. So they don't sum up to 1.0 due to the limitation of accuracy of the type.

You can also use rational numbers, which is in Data.Ratio module, instead of floating point numbers. In that case, they sum up to 1.0 when added together.
`import Data.Ratiohalf = (*) (1%2)prbTree x = x : prbTree y          where y = zipWith (+) (map half \$ 0:x) (map half \$ x++[0])`