11

現在、友人の OCaml プログラムを拡張しようとしています。これは、いくつかのデータ分析に必要な関数の膨大なコレクションです。

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

これがある種の「遅延」リストを実装していることはわかりましたが、実際にどのように機能するかはまったくわかりません。上記の型に基づいて Append 関数と Map 関数を実装する必要があります。誰もそれを行う方法を知っていますか?

どんな助けでも本当に感謝します!

4

3 に答える 3

7

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

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

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

type 'a llist = 'a cell Lazy.t

つまり、遅延セル値です。

マップの実装は、上記の定義に関してより意味があるかもしれません

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

一方

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

版画

foo
foo

違いは、式の値を1 回だけforce計算することです。

于 2009-01-10T14:56:51.743 に答える
7 
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 を介して関数 (専門用語ではクロージャー) にカプセル化されるということです。式 x は、関数が () (情報を含まない単位値) に適用された場合にのみ評価されます。

于 2009-01-10T12:03:43.123 に答える
1

はい、リストは無限にある可能性があります。他の回答で与えられたコードは無限リストの最後に追加されますが、無限リストの後に何が追加されるかを観察できるプログラムはありません。

于 2009-01-10T19:21:01.147 に答える