2021-06-04 Fri. — match 式とリストパターン
勉強
プログラミング in OCaml (–§5.2 リストの要素へのアクセス)
練習問題 4.6
fun x y -> y
を、コンビネータs
とk
を関数適用のみで組み合わせた形で表現する。
予想(間違っている)
s k x y --> k y (x y) (* ??? *) --> y
となってほしいけど、型付けエラーになる。実際型無しのコンビネータを考えるとこれでもいいみたい。全くわかってないけど難しいので今はやらない。
正解
恒等コンビネータi
をs k k
と表せるので、i
も使っていい。
y
をx y
に戻すにはどうすればいいか逆算する
y --> i y (* 恒等コンビネータ *) --> k i x y (* k で i の後ろに x を付け加えられる *) --> k (s k k) x y (* i を s k k とする *)
つまり、x y
にk (s k k)
に適用したらy
になる。
match
式
let rec sum_list l = match l with [] -> 0 | n :: rest -> n + (sum_list rest);;
パターン1 :: パターン2
は、先頭の要素をパターン1
に、残りのリストをパターン2
にマッチさせる。
n :: rest
は、先頭の要素がn
、残りのリストがrest
にマッチ。
sum_list [1; 2; 3; 4]
の挙動を考えてみる。
sum_list [1; 2; 3; 4] (* match with 1 :: [2; 3; 4] *) --> 1 + sum_list [2; 3; 4] (* match with 2 :: [3; 4] *) --> 1 + 2 + sum_list [3; 4] (* match with 3 :: [4] *) --> 1 + 2 + 3 + sum_list [4] (* match with 4 :: [] *) --> 1 + 2 + 3 + 4 + sum_list [] (* match with [] *) --> 1 + 2 + 3 + 4 + 0
ちゃんとリストの要素の和ができる。再帰関数の定義なので、
[]
: 空リストの場合の処理- コンスの場合の処理
を記述する。
このmatch
式は、
- 引数をパターンマッチング以外に使わず、
- 最後の引数に関して即座にパターンマッチングを行うとき
に以下のように略記できる(function
式)。
let rec sum_list l = ...
は、let rec sum_list = fun l -> ...
の略記だったことに注意しよう。
let rec sum_list l = match l with パターン1 -> 式1 | パターン2 -> 式2 ...
は、
let rec sumlist = function パターン1 -> 式1 | パターン2 -> 式2 ...
と略記できる。
map
リストの各要素に関数を適用する関数map
:
let rec map f = function [] -> [] | x :: rest -> f x :: map f rest;;
の挙動を確認しよう
map f [x; y; z] (* match with x :: [y; z] *) --> f x :: map f [y; z] (* match with y :: [z] *) --> f x :: f y :: map f [z] (* match with z :: [] *) --> f x :: f y :: f z :: [] (* match with [] *)\ --> [f x; f y; f z]
日記
断酒24日目。
プログラミング in OCaml。リストの章に入った。私は掃除ができない人間なので、きれいにデータを並べる偉大さを感じながら読む。
簡単な言語処理系を書きたい(『プログラミング言語の基礎概念』の演習問題を解くプログラムを書くため)というモチベーションで『プログラミング in OCaml』を 読み始めた。つまりまさに木構造などのデータ構造を操作したいので、この章まで読めてうれしい。とてもおもしろいのでまだまだ進む。