OCaml

unit 型を使った無限列表現

プログラミング in OCaml

unit型の無限列表現が少しわかりにくかったので、頭を整理する目的で、ちょっと考えてみた。

まず、unit 型。

(* unit型 *)
type 'a seq = Cons of 'a * (unit -> 'a seq);;
(* unit型の無限列表現 *)
let rec from n = Cons (n, fun () -> from (n+1));;

let Cons(x1, f1) = from 1
let Cons(x2, f2) = f1 ()
let Cons(x3, f3) = f2 ();;

まあ、こんな感じかなあ。

 from 1 => Cons(1, (Cons 2, (Cons 3 ……)

n 番目の要素を取得する関数 nthseq は、以下のようになるかな。

let rec nthseq n (Cons(x, f)) =
  if n = 1 then x
  else nthseq (n-1) (f ()) ;;

(* 実行例 *)
let test_nthseq = nthseq 5 (from 1) = 5;;   (* true *)

その無限列の各要素に関数を適用する。

  let rec mapseq f (Cons (x, tail)) =
    Cons (f x, fun () -> mapseq f (tail ()));;

各要素の逆数をとる関数 recipracal を定義。

let reciprocals = mapseq (fun x -> 1.0 /. float_of_int x) (from 2);;

無限列のはじめの n 要素をリストにする関数 take

let take n (Cons(x, f)) =
  let rec take_in n (Cons(x, f)) e =
    if n = 1 then e @ [x]
    else take_in (n-1) (f ()) (e @ [x] )
  in
  take_in n (Cons(x, f)) [];;

(* 実行例 *)
let test_take = take 5 reciprocals = 
    [0.5; 0.333333333333333315; 0.25; 0.2; 0.166666666666666657];;    (* true*)