2

Haskell では [1,2,3]1:2:3:[] の糖衣構文だと学びました。

import Data.List
isPrefixOf (1:[]) (1:2:3:[])
-- True

ですが厳密には1:[]はprefixになっていないと思えます。
1:[]:2:3:[] であれば確かにprefixと言えそうですがこれは[1:2:3]を解釈したものではないということをどう考えるべきですか?
実装か関数の説明、のリストの糖衣構文のどれかが正確ではないと思うのですが。

6
  • isPrefixOfの実装や挙動、というより、Haskellでの一般的な関数適用や演算子的なものの結合時の優先順位の話ですかね? Commented 2015年2月10日 8:04
  • 1:[]:2:3:[]は「文法的に誤り」ではないですよね。型エラーになりますが (IntとListを直接混ぜたリストは作れない)。 Listのみで構成されるようにすれば、[1]:[]:[2]:[3]:[] => [[1],[],[2],[3]] のように問題なく評価できます。
    – shirok
    Commented 2015年2月10日 12:20
  • ああ、言いたいことがわかりました>編集後の質問。 (:)の見かけが左右対象なので混乱しているのかなと思いました。(:)の左右は対象ではありません。回答欄で説明しますね。
    – shirok
    Commented 2015年2月11日 2:04
  • 第三者による質問編集により当初の疑問点(二つありました)のポイントが両方とも失われてしまっており、当惑を感じます Commented 2015年2月11日 2:10
  • ああ、第三者の編集だったのですか。
    – shirok
    Commented 2015年2月11日 2:37

2 件の回答 2

2

注意:元の質問が第三者により大幅に「編集」されており、この解答は現在の質問の答とは言い難くなっています。元の質問には二つの疑問がありました:

  • 糖衣構文と文字展開の違いに関する誤解による疑問
  • isPrefixOf の prefix を「リストがリストに含まれている」と解説している文章(出展不明)に対する疑問

もっともな質問であり解答に値する質問だと思います。


糖衣構文は C言語のマクロのような式の文字列どおりの置換ではなく、式の構造を壊さないように適宜括弧を補って考える必要があります。

isPrefixOf [1] [1,2,3]

を文字通り isPrefixOf 1:[] 1:2:3:[] と展開するのは間違いです。正しくは括弧を補った次の式、

isPrefixOf (1:[]) (1:2:3:[])

と等価です。

isPrefixOf は第一引数のリスト要素を先頭から見ていって、第二引数のリストの先頭から同じ順に現れるかどうかを調べる関数です。第二引数のリスト構造内に「同じリストが含まれている」ことを調べるものではありません。「含まれている」がどのような意味を持つのか不明ですが、あまり正確ではない解説で誤解されるのもしようがないのではないかという気がします。

どちらかというと、その説明は isSuffixOf の方に適しているかもしれません:

isSuffixOf [3,4] [1,2,3,4]

True になりますが、糖衣構文を展開した式、

isSuffixOf (3:4:[]) (1:2:3:4:[])

をご覧になると、第一引数のリスト構造が第二引数の構造内に含まれているのがわかります。

2

(:)の見た目が左右対象で、しかも右結合前提で括弧が省略されるのでわからなくなったのかなと思いました。

リストというのは、概念的にはこういうデータ構造です。

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:zx:(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]と書けると便利です。これを見比べれば、

  • [1,2,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]]

となるわけです。

1
  • Pair (Pair 1 Nil) (Pair Nil (Pair (Pair 2 Nil) Nil)) と展開できると納得出来ました ありがとうございます。
    – nitibo
    Commented 2015年2月11日 13:41

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。