Ocaml List：執行追加和映射功能

我正在嘗試擴展朋友的OCaml程序。這是所需要的一些數據分析功能的巨大集合。由於我不是一個真正的OCaml的裂縫目前我卡上（對我來說）陌生的List實現：Ocaml List：執行追加和映射功能

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

我已經想通了，這實現了某種「懶惰」列表，但我完全不知道它是如何工作的。我需要根據上面的類型實現一個Append和一個Map函數。有誰知道如何做到這一點？

任何幫助真的很感謝！

來源

2009-01-10 Chris

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));;

此實現懶惰名單的基本思想是每個計算是在一個函數（技術術語是關閉），通過有趣的封裝（） - > X。然後，只有函數應用於（）（單位值，不包含任何信息）時纔會評估x表達式。

來源

2009-01-10 12:03:43 starblue

它可以幫助需要注意的是函數閉基本上等同於懶惰值：

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

的區別在於force計算表達式的值恰好一次。

來源

2009-01-10 14:56:51

是的，列表可以是無限的。在其他答案中給出的代碼將追加到無限列表的末尾，但沒有可以編寫的程序，也不能觀察無限列表後面追加的內容。

來源

2009-01-10 19:21:01

Ocaml List：執行追加和映射功能

回答

相關問題