パスカルの三角形（みたび）

cf. id:rubyco:20060531:pascal
cf. id:epics:20060530:1149000099

Ruby の Enumerable#inject は Haskell では foldl だ。
というわけで早速やってみよう。ただし，無限リストを扱えるように foldr をつかう。早くしないと 結城さんに先を越されちゃうぞ。

 pascalTriangle = foldr (\n i ->  [pascal n] ++ i) [[]] [1..]
   where pascal x | x == 1    = [1]
                  | otherwise = (\xs -> zipWith (+) (0:xs) (xs ++ [0])) (pascal (x-1))

結果。

 *Main> putStr $ unlines $ map show $ take 10 $ pascalTriangle
 [1]
 [1,1]
 [1,2,1]
 [1,3,3,1]
 [1,4,6,4,1]
 [1,5,10,10,5,1]
 [1,6,15,20,15,6,1]
 [1,7,21,35,35,21,7,1]
 [1,8,28,56,70,56,28,8,1]
 [1,9,36,84,126,126,84,36,9,1]

あー，でも，n 列目を作るのに再帰してるのが無駄っぽいなぁ。