zipWith関数の中身を解説してみる
みなさん、こんにちは。どんぶラッコです。
最近 すごいHaskell という本を使って、関数型プログラミングについての勉強会を開催しています。
その中の5章、高階関数について紹介されている記事の中で zipWith
という関数を実装してみるという単元があるのですが、Haskellに慣れていないこともあり、まー解読に時間がかかりました。。
他にも僕のような思いをしている方がいらっしゃるかもしれないので、調べたことを書き残しておこうと思います。
プログラミングコード
完成したコードがこちら
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys
main = print ( zipWith' (+) [4,2] [2,3] ) -- [6,5] が出力される
paiza.ioにも転機しておいたので、確認したい方は↓↓から実行してみてください
https://paiza.io/projects/2O6Nxw8wEDbwe-GSRxgzcQ
実際に zipWith'
を実行しているのは最下行の
zipWith' (+) [4,2] [2,3]
です。
zipWith` それぞれの引数として +
演算子の中置関数、 [4,2]
のリスト、 [2,3]
のリストをそれぞれ渡し、それぞれのリストの項目に対して加算が実行されます。結果、 [6,5]
というリストが生成されるわけです。
今、「それぞれの引数」と引数を複数取れそうな表現をしてしまいましたが、Haskellの原則(というよりラムダ計算の原則)として、引数を1つしか取ることができません。でもそれをカリー化という手法を使うと複数の引数を扱えるかのように表現できます。この辺はまた別記事でご紹介します。
便宜上、この記事ではそれぞれの引数を 「第1引数」「第2引数」と表現します。
1. 関数の型定義
順を追って確認していきましょう。まずは型定義から。
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
Haskellの型定義は
関数名 :: 引数1 -> 引数2 -> ... -> 戻り値
という形式で表現されます。
これもHaskellは引数を複数取っているわけではないので正確な表現ではありません!
ここでは戻り値の型定義が一番最後に書かれるんだなー、ということがおさえておければOKです。
型変数
a
b
c
となっているのは、「型変数」と呼ばれるものでしたね。入力される引数に複数の型の可能性がある場合に指定できるものでした。
例えばこんな感じです。
double :: (Num a) => a -> a
double x = x + x
main = do
print( double 2 ) -- 4
print( double 1.5 ) -- 3.0
引数に入ってきた数字を2倍して返してくれるdouble
関数を作ってみました。
結果は 2 も 1.5 も一緒ですね。
しかし、2は整数、1.5は実数(小数)なのでそれぞれのデータ型は異なります。
なので、例えば型定義を Int
で宣言してしまうと、 引数 1.5 を入れた場合はエラーになってしまいます。
double :: Int -> Int
double x = x + x
main = do
print( double 2 ) -- 4
print( double 1.5 ) -- エラーが発生
コンパイルエラーの内容を見ると、
[1 of 1] Compiling Main ( Main.hs, Main.o )
Main.hs:17:19: error:
• No instance for (Fractional Int) arising from the literal ‘1.5’
• In the first argument of ‘double’, namely ‘1.5’
In the first argument of ‘print’, namely ‘(double 1.5)’
In a stmt of a 'do' block: print (double 1.5)
|
17 | print( double 1.5 )
| ^^^
Int のインスタンスじゃねーじゃねーか!と怒られています。
でも、整数であっても小数であっても、2倍の処理は実行できますよね。
そんなときに登場するのが型変数です。
double :: (Num a) => a -> a
(Num a) =>
の部分は、数字だったOKよという条件をつけてくれてるものだとここでは理解しておいてください(型クラス制約と言われます)。
なので、ここの型定義の意味は、数字である型の a
(仮名) が入ってきたら、戻り値が a
(仮名) が返る関数ですよ、ということを示しています。この a
が型変数です。概念を抽象化してくれているんですね。
なので、 引数が Int
型で戻り値が Int
でも成立しますし、 引数がFloat
型で戻り値が Float
でも成立するわけです。
型定義
長くなってしまいました。改めて型定義に戻りましょう。
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
ここでは、第1引数(便宜上そう表現します)に a
と b
を引数に取って c
を返す関数が入ります、と定義されています。 型変数がa, b, cとそれぞれ異なるので、それぞれは異なる型でもOKですということになっています。
これは、二項演算子を入れるための定義ですね。参考までに、 +
演算子の型定義を掲載しておきます。
ghci> :t (+)
(+) :: Num a => a -> a -> a
そして、第2引数、第3引数はそれぞれ [a]
[b]
となっています。こちらは aとbがかぶっているので、 (a -> b -> c)
内の a
と b
と型が一致していなければいけませんね。
ここで、zipWith'
の挙動を思い出してみてさい。
zipWith' (+) [4,2] [2,3] -- [6,5]が結果として出力される
つまり、
[4+2, 2+3]
が実行されて欲しいわけです。
なので、それぞれのリスト項目の足し算は左辺は第2引数の要素、右辺は第3引数の要素である必要があります。
左辺右辺、つまり (a -> b -> c)
の a
と b
と型が一致する必要がありますよね。
そして最後、戻り値として出力されるのは [c]
です。これも、a
と b
の計算結果 c
と型が一致している必要がありますよね!ということです。
'
(アポストロフィ) の意味慣習的に、正格評価の関数を示したり、バージョンを変更した似た関数に名前をつけるときに使います。今回の zipWith'
の場合、既に標準ライブラリとしての zipWith
があるため、アポストロフィをつけて関数名をつけています。
2. 関数本体の実装
引数を確認する
ではいよいよ、関数本体の実装をみていきましょう。
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys
これも最初「?」となりますが、1つひとつの処理を具体例を使って紐解いていけば難しいことはありません。
zipWith' (+) [4,2] [2,3]
が実行されたという前提で一つずつ処理を見ていきましょう。
すると、
f
には +
が束縛されます。
同様に、 (x:xs)
には [4,2]
、 (y:ys)
には [2,3]
が入ってきます。
x:xs ってなんじゃい? – コロン演算子とパターンマッチング
ここで、(x:xs)
って何?となる方もいると思うので、この部分を深掘りしていきます。
そもそも、Haskell においてコロン :
はコロン演算子、ないしはコンス(cons)演算子と呼ばれるものです。
なぜconsと呼ばれているかというと、これがリストを “construct (構築)” する役割があるためです。
main = print ( 1:[2,3] ) -- [1,2,3]
コロンの左に数字、右辺にリストを取ることで、両辺を結合した新しいリストを生成してくれます。
:
の型定義を確認してもそのような挙動になることが見て取れます。
ghci> :t (:)
(:) :: a -> [a] -> [a]
なので、[1,2,3,4]
は 1:2:3:4:[]
の糖衣と言い換えることができます。
ここで混乱してしまった方は、1:2:3:4:[]
を
1:(2:(3:(4:[])))
とも表現できる、と考えると腹落ちするかもしれません。
1:(2:(3:(4:[]))) -- 4:[] が実行され、[4]が作られる
1:(2:(3:([4])) -- 3:([4]) が実行され、[3,4]が作られる
1:(2:[3,4]) -- 2:[3,4] が実行され、[2,3,4]が作られる
1:[2,3,4] -- 1:[2,3,4] が実行され、[1,2,3,4]が作られる
[1,2,3,4] -- 完成!
ということですね!
さて、では (x:xs)
に話を戻しましょう。
先ほどまで議論していたコロン演算子が使われていますね。そして、ここに入ってくるのは [4,2]
という演算子でしたね。
[4,2]
という配列はコロン演算子を使うと
4:[2]
とも表現できますよね?
なので、x:xs
のパターンと一緒やんけ!ということでパターンマッチングが実行されます。つまり、 xに4, xsに[2] がそれぞれ代入されるのです!
x
と xs
の変数名はなんでもいいのですが、”使われることが多い”という理由です。 要素xとその要素xの配列ということで複数形のxs ということなのでしょう。
y:ys
と [2,3]
についても同様ですね。
関数の中身を確認する
では、本体を見ていきます。
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys
本体は f x y : zipWith' f xs ys
となっていますね。またわかりづらい…
ここでも具体例 zipWith' (+) [4,2] [2,3]
を使ってみていきましょう。
それぞれの変数に具体の数字を代入して考えてみます
zipWith' f (x:xs) (y:ys) = (+) 4 2 : zipWith' (+) [2] [3]
(+) 4 2
は つまり 4 + 2
ですね。中置関数である +
が (+)
とすることで先頭に持って来れているわけです。
そして zipWith' (+) [2] [3]
は、また zipwith'
を呼び出しています。再帰ですね。
それを先程説明したコロン :
で繋いでいます。
つまり、再帰された zipWith'
を展開するとこのようになります。
(+) 4 2 : zipWith' (+) [2] [3] -- zipWith' を展開
(+) 4 2 : (+) 2 3 : zipWith' (+) [] [] -- zipWith' を展開 (結果が[]になる理由は後述)
(+) 4 2 : (+) 2 3 : [] -- わかりやすくするため 加算を先に実施した体にする
6 : 5 : []
[ 6, 5 ]
結果まで辿り着きましたね!
最後の戻り値が [] になるパターンを作成
ここで、 zipWith' (+) [] []
の戻り値が []
になるのはなんで?と思ったかたもいらっしゃるでしょう。
これは、パターンマッチと呼ばれるhaskell特有の文法パターンを用いているためです。
関数本体の上にいくつか謎の式が書かれていることが気になった方もいらっしゃると思います。
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = [] -- この行と
zipWith' _ _ [] = [] -- この行
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys
ここが、戻り値が []
になる理由です。
つまり、第2引数の値が []
だった場合、あるいは 第3引数の引数が []
だった場合は、空の配列 ( []
) をreturnするようになっているわけです。
_
というのは、特に使わない引数のときに使います。例えば第1引数は使いませんが、以下のように書いてしまうと []
が第1引数になってしまいますよね。
zipWith' [] = ... -- 引数が1つだけになってしまうので 第1引数が [] とみなされる
また、zipWith' _ [] _ = []
と zipWith' _ _ [] = []
がバラバラの行で記述されている理由は、第2引数と第3引数の配列の長さが異なっている場合の対策です。
例えば zipWith' (+) [4,2] [2]
を実行したとしましょう。
すると、このようなプロセスをたどります。
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys -- 値を適用
(+) 4 2 : zipWith' (+) [4] [] -- (+) [4] [] は _ _ [] のパターンに合致する
(+) 4 2 : []
[6]
この記事のまとめ
いかがだったでしょうか?最初は「なんじゃこれ?」と思うものでも、一つずつ紐解いていけば難しくないですよね。
関数型言語の思想を知りたくて勉強を始めたHaskellですが、無駄が削ぎ落とされた記述方法が美しいなと思っています。文系出身ですが笑
勉強会を進める中で新しい気づきを得たらまたここに書いていこうと思います!