

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

[code]

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

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


CC BY-SA 3.0
2015-02-10T07:50:42.040
6250
2015-02-11T19:15:41.280
2015-02-11T13:38:04.900
8198
8198
question
haskell
haskellのisPrefixOfについて


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

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

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

* * *

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

[code]

    isPrefixOf [1] [1,2,3]
    
[/code]

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

[code]

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

と等価です。

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

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

[code]

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

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

[code]

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

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


CC BY-SA 3.0
2015-02-10T08:42:38.717
6253
2015-02-11T02:15:34.453
2015-02-11T02:15:34.453
898
898
6250
answer


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

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

[code]

    data List x = Nil | Pair x (List x)
    
[/code]

型`x`の要素をもつリスト`List x`とは、空リスト(`Nil`で表記)か、要素そのものと`List
x`から作られるペアである、ということです。(終わりがある場合は)最後が必ず`Nil`になります。

[code]

    Nil
    
[/code]

とだけあれば空のリスト。

[code]

    Pair 1 Nil
    
[/code]

なら「1」をひとつの要素として持つ長さ1のリスト。  
従って1, 2, 3からなるリストならこうなります。

[code]

    Pair 1 (Pair 2 (Pair 3 Nil))
    
[/code]

最後の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]`と書けると便利です。これを見比べれば、

  * `[1,2,3]` ≡ `1:2:3:[]`

という対応があることがわかると思います。最後に`[]`が「付け加わった」のではないことに注意。

さて、`isPrefixOf` は次のとおり定義できます。

[code]

    isPrefixOf Nil _          = True
    isPrefixOf (Pair a b) Nil = False
    isPrefixOf (Pair a b) (Pair c d) = a == c && isPrefixOf b d
    
[/code]

つまり、第一引数が先にNilになったら真。第二引数の方が先に尽きちゃったら偽。両方ともペアの場合、現在の要素を比べて、それが等しければ「残りの要素同士」を比べる。

質問にある例をこの表記に置き換えて:

[code]

    isPrefixOf (Pair 1 Nil) (Pair 1 (Pair 2 (Pair 3 Nil)))
    
[/code]

動作を追ってみてください。

ここからは余談ですが、Nilを要素に含むリストというのももちろん考えることができます。整数とリストは混ぜられないので、「リストのリスト」を考えます。見やすいように

[code]

    x1 = Pair 1 Nil  -- 要素'1'だけからなる長さ1のリスト
    x2 = Pair 2 Nil  -- 要素'2'だけからなる長さ1のリスト
    
[/code]

と定義しておいて

[code]

    Pair x1 (Pair Nil (Pair x2 Nil))
    
[/code]

といった具合にリストを作れます。これは全て展開すれば次と同じであり:

[code]

    Pair (Pair 1 Nil) (Pair Nil (Pair (Pair 2 Nil) Nil))
    
[/code]

`(:)`と`[]`に置き換えれば:

[code]

    (1:[]):[]:(2:[]):[]
    
[/code]

内側のリストだけ糖衣構文にすれば:

[code]

    [1]:[]:[2]:[]
    
[/code]

全てを糖衣構文にすれば:

[code]

    [[1],[],[2]]
    
[/code]

となるわけです。


CC BY-SA 3.0
2015-02-11T02:36:20.210
6289
2015-02-11T19:15:41.280
2015-02-11T19:15:41.280
5258
5258
6250
answer