(:)の見た目が左右対象で、しかも右結合前提で括弧が省略されるのでわからなくなったのかなと思いました。
リストというのは、概念的にはこういうデータ構造です。
data List x = Nil | Pair x (List x)
型x
の要素をもつリストList x
とは、空リスト(Nil
で表記)か、要素そのものとList x
から作られるペアである、ということです。(終わりがある場合は)最後が必ずNil
になります。
Nil
とだけあれば空のリスト。
Pair 1 Nil
なら「1」をひとつの要素として持つ長さ1のリスト。
従って1, 2, 3からなるリストならこうなります。
Pair 1 (Pair 2 (Pair 3 Nil))
最後のNilはリストの要素ではなく、リストの終端を表しているだけです。これを普通のリスト表記で書くと[1,2,3]
ということになり、Nil
はどこにも出てきません。
ここで、
Pair(x, y)
を x:y
と書く
Nil
を []
と書く
- 中置演算子
(:)
は右結合、つまり x:y:z
は x:(y:z)
を意味する
と決めて上の例を置き換えると
[]
は空リスト
1:[]
は要素1だけを持つ長さ1のリスト
1:(2:(3:[]))
は1, 2, 3からなる長さ3のリスト。結合法則を利用して括弧を省略すれば 1:2:3:[]
となります。
一方、構文糖衣として、要素1だけを持つ長さ1のリストを [1]
、要素1,2,3からなる長さ3のリストを[1,2,3]
と書けると便利です。これを見比べれば、
という対応があることがわかると思います。最後に[]
が「付け加わった」のではないことに注意。
さて、isPrefixOf
は次のとおり定義できます。
isPrefixOf Nil _ = True
isPrefixOf (Pair a b) Nil = False
isPrefixOf (Pair a b) (Pair c d) = a == c && isPrefixOf b d
つまり、第一引数が先にNilになったら真。第二引数の方が先に尽きちゃったら偽。両方ともペアの場合、現在の要素を比べて、それが等しければ「残りの要素同士」を比べる。
質問にある例をこの表記に置き換えて:
isPrefixOf (Pair 1 Nil) (Pair 1 (Pair 2 (Pair 3 Nil)))
動作を追ってみてください。
ここからは余談ですが、Nilを要素に含むリストというのももちろん考えることができます。整数とリストは混ぜられないので、「リストのリスト」を考えます。見やすいように
x1 = Pair 1 Nil -- 要素'1'だけからなる長さ1のリスト
x2 = Pair 2 Nil -- 要素'2'だけからなる長さ1のリスト
と定義しておいて
Pair x1 (Pair Nil (Pair x2 Nil))
といった具合にリストを作れます。これは全て展開すれば次と同じであり:
Pair (Pair 1 Nil) (Pair Nil (Pair (Pair 2 Nil) Nil))
(:)
と[]
に置き換えれば:
(1:[]):[]:(2:[]):[]
内側のリストだけ糖衣構文にすれば:
[1]:[]:[2]:[]
全てを糖衣構文にすれば:
[[1],[],[2]]
となるわけです。