Haskellで有名アルゴリズム実装（5）

最近英語力が落ちてる感があるので、英語で書く。

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.Ratio

half = (*) (1%2)
prbTree x = x : prbTree y
          where y = zipWith (+) (map half $ 0:x) (map half $ x++[0])

Go to Haskell's page.