結城浩のHaskell日記 RSSフィード

2006-06-01

パスカルの三角形 パスカルの三角形 - 結城浩のHaskell日記 を含むブックマーク

パスカルの三角形を作ります。とりあえずリストのリストで。

choose :: Integer -> Integer -> Integer
choose n k | k == 0 = 1
           | k == n = 1
           | otherwise = c11 + c10
               where
                 c11 = choose (n-1) (k-1)
                 c10 = choose (n-1) (k-0)

chooseList :: Integer -> [Integer]
chooseList n = [ choose n k | k <- [0..n] ]

pascal :: Integer -> [[Integer]]
pascal n = [ line | line <- map chooseList [0..n]]

実行結果です。

*Main> pascal 0
[[1]]
*Main> pascal 1
[[1],[1,1]]
*Main> pascal 2
[[1],[1,1],[1,2,1]]
*Main> pascal 3
[[1],[1,1],[1,2,1],[1,3,3,1]]
*Main> pascal 4
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
*Main> pascal 5
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]

追記:sumimさんから、無限リストの解が到着いたしました。すごいなあ。

pascal = [1] : [[1] ++ zipWith (+) xs (tail xs) ++ [1] | xs <- pascal]

実行結果です。

*Main> take 5 pascal
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
*Main> take 1 $ drop 9 pascal
[[1,9,36,84,126,126,84,36,9,1]]

追記:sumimさんから、「!!を試そう」というコメントが。ふうん。

*Main> pascal !! 9
[1,9,36,84,126,126,84,36,9,1]

追記:nobsun経由でHanataniさんの作品を教えてもらいました。これ「ずらして足しあわす」という趣がありますね。

pascal = [1]:[zipWith (+) ([0]++p) (p++[0]) | p <- pascal]
-- by Hanataniさん

sumimsumim2006/06/01 23:28お邪魔します。リストのリストでしたら、こんなのではいかがでしょう。
pascal = [1] : [[1] ++ zipWith (+) xs (tail xs) ++ [1] | xs <- pascal]

sumimsumim2006/06/02 00:2810 個目の要素が欲しいときは、こんなふうにするとよいと思います。
pascal !! 9

nobsunnobsun2006/06/02 09:34pascal = [1]:[zipWith (+) ([0]++p) (p++[0]) | p <- pascal]
(by Hanataniさん)

nobsunnobsun2006/06/02 09:37:info (または :i)というのも便利ですよ.
ghciだと,
Prelude> :i True
data Bool = ... | True -- <wired into compiler>
Prelude> :i Bool
data Bool = False | True -- <wired into compiler>
instance Bounded Bool -- Imported from GHC.Enum
instance Enum Bool -- Imported from GHC.Enum
instance Eq Bool -- Imported from GHC.Base
instance Ord Bool -- Imported from GHC.Base
instance Read Bool -- Imported from GHC.Read
instance Show Bool -- Imported from GHC.Show
とか...

nobsunnobsun2006/06/02 09:43こんな定義はいかが?
(fibs0, fibs1) = (0:fibs1, 1:zipWith (+) fibs0 fibs1)
fib = (fibs0 !!)

[1..100]>>=pen[1..100]>>=pen2006/06/02 10:21http://hpcgi2.nifty.com/1to100pen/wiki/wiki.cgi?p=%CB%E8%C6%FCHaskell の 2006-05-12 パスカルの三角形で同じようなことやりました。

sumimsumim2006/06/02 12:18Hanatani さん版、美しいですね。(._.) φ メモメモ w

IO ()IO ()2006/06/02 23:07iterate (\xs -> zipWith (+) (0:xs) (xs ++ [0])) [1] (by takatohさん)