背景
関数型プログラミング言語に興味があり、
以下のサイトでHaskellを勉強している。
https://learnyouahaskell.com/
（日本語の本も出ているみたい：https://www.amazon.co.jp/dp/4274068854 ）
リストについてのチャプターで
Haskellでは<、<=、>、そして>=で
リストの比較が行え、
辞書式順序で比較すると説明されているのだが
その挙動がなかなか理解できず、
日本語の記事も見つけられなかった。
同じことで悩んでいる人のためにメモを残す。
ハマったところ
リストの比較は以下のように書けるのだが、
なぜこれがFalseになるのかわからなかった。
ghci> [10,20] > [15,15]
False
10 > 15はFalseだが、
20 > 15はTrueなので、
「ひとつでもFalseがあればFalseになるのか？」と考えたが、
一方で以下の例はTrueになる。
ghci> [20,10] > [15,15]
True
わからない🤔
なぜこうなるのか？
こうなる理由は、
辞書式順序での比較というのが
次のように行われるため。
- まず最初の要素を比較
- それらが等しいなら2番目の要素を比較
- それらが等しいなら3番目の要素を比較
- （繰り返す）
例えば、次のような例を見てみる。
ghci> [1,2,10,0] > [1,2,0,10]
True
これは以下のようなステップで比較される。
-
1 > 1を比較 → 等しいので次へ -
2 > 2を比較 → 等しいので次へ -
10 > 0を比較 → 等しくない、10の方が大きいのでTrueを返す
最初の例に戻って確認
ghci> [10,20] > [15,15]
False
-
10 > 15を比較 → 等しくない、10の方が小さいのでFalseを返す
ghci> [20,10] > [15,15]
True
-
20 > 15を比較 → 等しくない、20のほうが大きいのでTrueを返す
==の場合どうなるのか？
==の場合でも同じ考え方が適用できる。
以下の例を見てみる。
ghci> [1,20] == [1,3]
False
-
1 == 1を比較 → 等しいので次へ -
20 == 3を比較 → 等しくない、Falseを返す
まとめ
Haskellのリストの比較は辞書式順序で行われる。
つまり、先頭から見ていって、
等しくない要素同士が出てきて初めて比較する。
ちゃんと書いてあったのだが、
「たぶんこういう挙動だろう」という先入観があって
読み間違えてしまっていた。。
Lists can be compared if the stuff they contain can be compared. When using <, <=, > and >= to compare lists, they are compared in lexicographical order. First the heads are compared. If they are equal then the second elements are compared,
参考