週末デッドエンド

勉強と日記と怪文書

2021-06-05 Sat. — リストの操作、クイックソート

プログラミング OCaml 日記 プログラミング in OCaml

勉強

プログラミング in OCaml (–§5.4 Case Study: 整列アルゴリズム)

畳み込み関数fold

何やってるのかわからないのでトレースする。

let rec fold_right f l e =
    match l with
    [] -> e
    | x :: rest -> f x (fold_right f rest e);;

fold_right ( + ) [3; 4; 5] 0 (*　[3; 4; 5] match with 3 :: [4; 5] *)
--> ( + ) 3 (fold_right ( + ) [4; 5] 0) (* [4; 5] match with 4 :: [5] *)
--> ( + ) 3 ( ( + ) 4 (fold_right) ( + ) [5] 0) (* [5] match with 5 :: [] *)
--> ( + ) 3 ( ( + ) 4 ( ( + ) 5 (fold_right ( + ) [] 0))) (* [] match with [] *)
--> ( + ) 3 ( ( + ) 4 ( ( + ) 5 ( 0 ) ) )
--> ( + ) 3 ( ( + ) 4 5) (* 一番右から ( + ) されていく *)
--> ( + ) 3 9
--> 12

もう1個わかんないやつ

let rec nth n l =
    match with (n, l)
    (1, a :: _) -> a
    | (_, _ :: rest) -> nth (n - 1) rest;;

nth 3 [3; 1; 4; 1] (* match with (_, _ :: [1; 4; 1]) *)
--> nth 2 [1; 4; 1] (* match with (_, _ :: [4; 1]) *)
--> nth 1 [4; 1] (* match with (1, 4 :: [1]) *)
--> 4

書いたら動作はわかるけど、自分でこの再帰関数を定義するの難しそう。

§5.4 Case Study: 整列アルゴリズム

ここで生成している擬似乱数列(一見ランダムに並んでいるように見える数列)は、乗算合同法(Lehmer乱数生成)というやり方。

https://en.wikipedia.org/wiki/Lehmer_random_number_generator

に載っている。

漸化式で定義される数列で、

x_{n + 1} = a \cdot x_n \mod m

と定義される。これを並べるとランダムに見える数列ができる。数列中に同じ数が出てくると以下ループする。うまいこと初期値(シードとも呼ぶ)と a と m を決めれば長いことループしない手頃な擬似乱数列ができる。

a =16807 ( = 7^5 ) 、 m = 2147483647 ( = 2^{31} -1 ) とするとうまいこといくらしい。

let nextrand seed =
    let a = 16807. and m = 2147483647. in
        let t = a *. seed
        in t -. m *. floor (t /. m);;

で漸化式を定義して、

let rec randlist n seed tail =
    if n = 0 then (seed, tail)
    else randlist (n - 1) (nextrand seed) (seed::tail);;

で、 n 項目までの擬似乱数列のリストを返す。

クイックソート

リストを適当な要素(pivotとする)を基準に2つに分ける関数partitionを考える。

素朴にpartitionするとき:

let rec partition pivot = function
  [] -> ([], [])
  | y :: rest ->
  let (left, right) = partition pivot rest in
  if pivot < y then (left, y::right) else (y::left, right);;

これだと末尾再帰的ではない。

これを末尾再帰的にするために、分割の途中までの結果をストアしておく変数を明示的に与えよう。

let rec partition left right pivot = function (* 末尾再帰的 *)
    [] -> (left, right)
    | y :: rest ->
        if pivot < y then partition left (y::right) pivot rest
        else partition (y::left) right pivot rest;;

then``else以下、最後に再帰を呼び出せるようになった。

let rec quick_sort = function
    [] -> []
    | pivot :: rest ->
        let (left, right) = partition [] [] pivot rest in
        quick_sort left @ (pivot :: quick_sort right);;

ここで、partitionを、quick_sortのpivotの有効範囲内で局所関数として組み込んじゃう。

let rec quick_sort = function
    [] -> []
    | pivot :: rest -> 
        (* ここで partition を定義する *)
        let rec partition left right = function (* pivot はもう渡されているので定義には不要 *)
            [] -> (left, right)
            | y :: ys -> (* rest は既使用なので ys にする *)
                if pivot < y then partition left (y::right) ys (* ここにも pivot 不要 *)
                else partition (y::left) right ys
            (* partition の局所定義終了 *)
        in
        let (left, right) = partition [] [] rest in
        quick_sort left @ (pivot :: quick_sort right);;

これでもいいのだが、最後にまだ工夫する。

let rec quick_sort = function
    ( [] | [_] ) as l -> l (* 1要素のときも自明な変形なので特別扱いする。後述 *)
    | pivot :: rest ->
        let rec partition left right = function
            [] -> (quick_sort left) @ (pivot :: quick_sort right) (* 呼び出したらすぐくっつけるので、その処理を partition の中に組み込む *)
            | y :: ys ->
                if pivot < y then partition left (y::right) ys
                else partition (y::left) right ys
        in partition [] [] rest;;
  • この関数の冒頭で( [] | [_] ) と書いてあるが、これは複数のパターンを|で区切って並べる or パターン。
    • |で繋がれている各パターンで宣言されている変数は同じでなくてはならない(( [] | [x] )とかはダメ)。
  • パターン as 変数は as パターン。内側のパターンがマッチしたときのみasパターン全体がマッチする。そして変数を内側のパターンにマッチした値に束縛する。
    • この関数では、lが長さ 1 以下のリスト全体に束縛される。

Tips

日記

断酒25日目。

今日は甥っ子の世話をしていた。昼寝をした。

関数型プログラミングを学び始めて、見えている地平が少しずつ広がっていく。

明日やりたいこと