データコンストラクタによるパターンマッチ
データコンストラクタによるパターンマッチというと、例えば、以前に Person 型を定義して、Show クラスのインスタンスにしたときに実装した show メソッドの引数での利用が挙げられる。(cf. Haskell で代数的データ型の値を print で出力には)
data Person = Person {name :: String,
age :: Int}
instance Show Person where
show (Person name age) = "Person: " ++ name ++ ", " ++ show age
main = print (Person "Tarou" 20)
リストにも当然ながらデータコンストラクタが存在する。(cf. ふつうのHaskellプログラミング , p.173) 普段よく見る「リストによるパターンマッチ」、
(x:xs)
「エラトステネスのふるい」でも、リストの先頭要素 p と、先頭以外のリスト ps にパターンマッチさせている。
sieve (p:ps) =
p : sieve [n|n <- ps, n ‘mod‘ p /= 0]
こういうのがリストのパターンマッチだと最初頭に入れてしまったので、それ以外の方法が頭の隅から追いやられてしまっていた。 (@_@;) それに気づかされたのが、Haskell (programming language) - Wikipedia, the free encyclopedia に書かれていた「逆ポーランド記法」を計算するための関数の例。
calc :: String -> [Float]
calc = foldl f [] . words
where
f (x:y:zs) "+" = y+x:zs
f (x:y:zs) "-" = y-x:zs
f (x:y:zs) "*" = y*x:zs
f (x:y:zs) "/" = y/x:zs
f xs y = read y : xs
(Haskell (programming language) - Wikipedia, the free encyclopedia より)
(cf. Python で逆ポーランド記法の計算)
リストのデータコンストラクタ
これを理解する前に、まずはリストについて調べておく。 Haskell においてリストは特別な立場にある。
The Haskell 98 Report: 定義ずみの型とクラス によると、
data [a] = [] | a : [a] deriving (Eq, Ord)
リストは、二つの構築子をもつ代数的データ型であるが、3.7 節で述べたように特別な構文をもつ。最初 の構築子は空リストで、`[]' (「ニル」)と書く。二つ目の構築子 は、`:' (「コンス」)と書く。
「コンス」というのは `constructor’ から来ている。以下を参照。
上記の引用にあるように : , [] は特別な構文。他のデータコンストラクタとは違う形をしている。そのため、関数における引数のパターンマッチにおいて、「これはデータコンストラクタによるパターンマッチなんだ。」という意識が薄れてしまっていた。
先ほどの逆ポーランド記法の計算に戻る。where 節の中の f 関数の引数を見ると、
(x:y:zs)
最初、「あれ？何で 3 つもあるの？」と思ってしまった。 ^^;
結局これもデータコンストラクタなんだから、以下のようにリストを生成したときのコンストラクタの使い方と対応している。
Prelude> 1:2:[3..10] [1,2,3,4,5,6,7,8,9,10]
パターンマッチの視点から見ると、リストを次のようにバラしている。
- 先頭の要素
- 先頭の次の要素
- 残りの要素のリスト
foldl
fold についても復習。(cf. Haskell の foldl , foldr)
型、要素を足し合わせていく方法、要素をリストにまとめていく方法について確認。
Prelude> :t foldl foldl :: (a -> b -> a) -> a -> [b] -> a Prelude> foldl (+) 100 [1..10] 155 Prelude> foldl (\x y -> x ++ [y]) [] [1..10] [1,2,3,4,5,6,7,8,9,10]
これを前提として、先ほどの逆ポーランド法の計算を見ていく。例えば、次のように calc を呼出したとすると、
calc = "1 2 + 3 *" calc = foldl f [] ["1","2","+","3","*"]
関数 f は先ほど foldl の型で見たように、二つの引数を取るので、最初は…
あれ？ イメージできない。パタッ(o_ _)ｏ~†
foldl の動作を手動で
仕方がないので、calc 関数をばらして、f を独立した関数に変更し、動作を試すことに。
calc :: String -> [Float] calc = foldl f [] . words f (x:y:zs) "+" = y+x:zs f (x:y:zs) "-" = y-x:zs f (x:y:zs) "*" = y*x:zs f (x:y:zs) "/" = y/x:zs f xs y = read y : xs
これをファイルに保存して、GHCi 上で :l によりロード。:t f で関数 f の型を見ると、
f :: (Fractional a, Read a) => [a] -> [Char] -> [a]
以下の計算を手動で試してみる。
*Main> calc "1 2 3 4 5 / - * +" [5.4]
f 関数の呼出しを繰り返し…
*Main> f [] "1" [1.0] *Main> f [1.0] "2" [2.0,1.0] *Main> f [2.0,1.0] "3" [3.0,2.0,1.0] *Main> f [3.0,2.0,1.0] "4" [4.0,3.0,2.0,1.0] *Main> f [4.0,3.0,2.0,1.0] "5" [5.0,4.0,3.0,2.0,1.0] *Main> f [5.0,4.0,3.0,2.0,1.0] "/" [0.8,3.0,2.0,1.0] *Main> f [0.8,3.0,2.0,1.0] "-" [2.2,2.0,1.0] *Main> f [2.2,2.0,1.0] "*" [4.4,1.0] *Main> f [4.4,1.0] "+" [5.4]
あ～ (@_@) なるほど、そういうことか。
再掲。
calc :: String -> [Float]
calc = foldl f [] . words
where
f (x:y:zs) "+" = y+x:zs
f (x:y:zs) "-" = y-x:zs
f (x:y:zs) "*" = y*x:zs
f (x:y:zs) "/" = y/x:zs
f xs y = read y : xs
0コメント:
コメントを投稿