

[Concepts, Techniques, and Models of Computer Programming (MIT
Press)](http://www.epsa.org/forms/uploadFiles/3B6300000000.filename.booksingle.pdf)

で取り上げられているパスカルの三角形（で日本語訳は正しいでしょうか）に関するfunctionにcons( list pair) のpattern
matching が用いられていますがelementはどのように追加され機能するのか教えてください。以下コード全文です。言語： _oz_

* * *
[code]

        declare Pascal AddList ShiftLeft ShiftRight fun {Pascal N}
    if N==1 then [1] else
    {AddList {ShiftLeft {Pascal N-1}} {ShiftRight {Pascal N-1}}}
    end end
    
    fun {ShiftLeft L} case L of H|T then H|{ShiftLeft T}
    else [0] end end
    fun {ShiftRight L} 0|L end
    
    fun {AddList L1 L2} case L1 of H1|T1 then
    case L2 of H2|T2 then H1+H2|{AddList T1 T2}
    end
    else nil end
    end
    
[/code]

* * *

ShiftLeftとAddListに用いられているのが分かると思います。いくらグーグルしても探し方なのかなかなかまとまった情報がなかったので少し読み進める前に最後の切り札として質問してみることにしました。よろしくお願いします。


CC BY-SA 3.0
2017-01-16T11:06:32.887
31889
2017-03-22T11:47:08.227
2017-03-22T11:47:08.227
3510
20242
question
prolog
list pairのpattern matchingの計算


的外れな回答になっていたら申し訳ありません。

まず、コメントを見る限りでは、`1`のような整数と`[1]`のような整数のリストが混ざってしまっているように見受けられます。
`Pascal`関数の引数は整数ですが、それ以外の`Pascal`の返り値、`ShiftLeft`、`ShiftRight`、`AddList`の引数および返り値は整数のリストです。

それからもう一つ、case instructionの解釈を間違ってしまっているのかなと思います。 `case L of
H|T`とある時、`H|T`は新しいリストを作っているのではなく、リスト`L`を「先頭要素`H`」と「後続のリスト`T`」に分解しています。

以上を基に、コメントの`{ShiftLeft {Pascal 1}}`を具体例として見てみると、 まず`{Pascal
1}`の計算結果は`Pascal`関数の定義から`[1]`です。 これに対して`ShiftLeft`が適用されるので、`L`のはじめの値は`[1]`です。
これはパターン`H|T`にマッチして、`H`=`1`、`T`=`nil`と分解され、then分岐へと進みます。 次に`1|ShiftLeft
nil`を計算しますが、`ShiftLeft
nil`は（nilがパターンにマッチしないのでelseへ進んで）`[0]`を返すので、全体としては`1|[0]`=`[1 0]`となります。


CC BY-SA 3.0
2017-01-18T13:35:58.560
31952
2017-01-18T13:35:58.560
13199
31889
answer