週末デッドエンド

勉強と日記と怪文書

2021-06-04 Fri. — match 式とリストパターン

勉強

プログラミング in OCaml (–§5.2 リストの要素へのアクセス)

練習問題 4.6

fun x y -> yを、コンビネータskを関数適用のみで組み合わせた形で表現する。

予想(間違っている)
s k x y
--> k y (x y) (* ??? *)
--> y

となってほしいけど、型付けエラーになる。実際型無しのコンビネータを考えるとこれでもいいみたい。全くわかってないけど難しいので今はやらない。

正解

恒等コンビネータis k kと表せるので、iも使っていい。

yx yに戻すにはどうすればいいか逆算する

y
--> i y (* 恒等コンビネータ *)
--> k i x y (* k で i の後ろに x を付け加えられる *)
--> k (s k k) x y (* i を s k k とする *)

つまり、x yk (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

ちゃんとリストの要素の和ができる。再帰関数の定義なので、

  1. []: 空リストの場合の処理
  2. コンスの場合の処理

を記述する。

この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』を 読み始めた。つまりまさに木構造などのデータ構造を操作したいので、この章まで読めてうれしい。とてもおもしろいのでまだまだ進む。