Ocamlリスト：追加機能とマップ機能を実装する

Question

現在、友人のOCamlプログラムを拡張しようとしています。これは、いくつかのデータ分析に必要な関数の膨大なコレクションです。私は実際にはOCamlクラックではないので、現在（私にとって）奇妙なList実装にこだわっています：

type 'a cell = Nil
    | Cons of ('a * 'a llist)
and 'a llist = (unit -> 'a cell);;

これにより、ある種の「怠laz」が実装されることがわかりました。リスト、しかし、私はそれが実際にどのように機能するか全くわからない。上記のタイプに基づいて、追加とマップ関数を実装する必要があります。誰かがそれを行う方法を知っていますか？

ご協力いただければ幸いです！

Answer 1

let rec append l1 l2 = 
    match l1 () with
        Nil -> l2 | 
        (Cons (a, l)) -> fun () -> (Cons (a, append l l2));;

let rec map f l =
    fun () -> 
        match l () with
            Nil -> Nil | 
            (Cons (a, r)) -> fun () -> (Cons (f a, map f r));;

この遅延リストの実装の基本的な考え方は、各計算がfun（）を介して関数（技術用語はクロージャー）にカプセル化されることです。バツ。 式xは、関数が（）（情報を含まない単位値）に適用された場合にのみ評価されます。

Answer 2

関数のクロージャーは遅延値と本質的に同等であることに注意してください：

lazy n : 'a Lazy.t    <=>    (fun () -> n) : unit -> 'a
force x : 'a          <=>    x () : 'a

したがって、タイプ 'a llist は次と同等です

type 'a llist = 'a cell Lazy.t

i.e。、遅延セル値。

マップの実装は、上記の定義の観点からより意味があります

let rec map f lst =
  match force lst with
    | Nil -> lazy Nil
    | Cons (hd,tl) -> lazy (Cons (f hd, map f tl))

それをクロージャーに戻す：

let rec map f lst =
  match lst () with
    | Nil -> (fun () -> Nil)
    | Cons (hd,tl) -> (fun () -> Cons (f hd, map f tl))

同様に追加あり

let rec append a b =
  match force a with
    | Nil -> b
    | Cons (hd,tl) -> lazy (Cons (hd, append tl b))

なる

let rec append a b =
  match a () with
    | Nil -> b
    | Cons (hd,tl) -> (fun () -> Cons (hd, append tl b))

何が起こっているかをより明確にするため、一般的に lazy 構文を使用することを好みます。

また、遅延サスペンションとクロージャーは、完全に同等ではないことに注意してください。たとえば、

let x = lazy (print_endline "foo") in
  force x;
  force x

印刷

foo

whereas

let x = fun () -> print_endline "foo" in
  x ();
  x ()

印刷

foo
foo

違いは、 force は式の値を exactly once で計算することです。

Answer 3

はい、リストは無限にすることができます。他の回答で与えられたコードは、無限リストの最後に追加されますが、無限リストの後に追加されるものを観察できるプログラムを書くことはできません。