Danh sách Ocaml: Thực hiện chức năng chắp thêm và bản đồ

Question

Tôi hiện đang cố gắng mở rộng chương trình OCaml của một người bạn. Đó là một bộ sưu tập khổng lồ các chức năng cần thiết cho một số phân tích dữ liệu .. Vì tôi không phải là thực sự là một vết nứt OCaml Tôi hiện đang bị mắc kẹt trên một (cho tôi) Danh sách lạ thực hiện:

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

tôi đã tìm ra rằng điều này thực hiện một số loại "lười biếng" danh sách, nhưng tôi hoàn toàn không có ý tưởng làm thế nào nó thực sự hoạt động. Tôi cần phải thực hiện một chức năng Phụ lục và Bản đồ dựa trên loại trên. Có ai có ý tưởng làm thế nào để làm điều đó?

Bất kỳ trợ giúp nào thực sự sẽ được đánh giá cao!

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

Ý tưởng cơ bản của việc thực hiện danh sách lười này là mỗi tính toán được đóng gói trong một hàm (thuật ngữ kỹ thuật là đóng) qua fun() -> x. Biểu thức x sau đó chỉ được đánh giá khi hàm được áp dụng cho() (giá trị đơn vị, không chứa thông tin).

Answer 2

Nó có thể giúp cần lưu ý rằng chức năng đóng cửa cơ bản là tương đương với giá trị lười biếng:

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

Vì vậy, các loại 'a llist tương đương với

type 'a llist = 'a cell Lazy.t 

ví dụ, một giá trị của ô lười biếng.

Một thực hiện bản đồ có thể có ý nghĩa hơn về định nghĩa trên

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

Dịch mà trở lại đóng cửa:

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

Tương tự như vậy với append

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

trở thành

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

Tôi thường thích sử dụng cú pháp lazy, vì nó làm cho nó rõ ràng hơn những gì đang diễn ra.

Lưu ý, cũng có nghĩa là hệ thống treo lười và đóng cửa không phải là chính xác tương đương. Ví dụ,

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

in

foo 

trong khi

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

in

foo 
foo 

Sự khác biệt là force tính giá trị của biểu thức chính xác một lần.

Answer 3

Có, danh sách có thể là vô hạn.Mã được đưa ra trong các câu trả lời khác sẽ nối vào cuối danh sách vô hạn, nhưng không có chương trình nào bạn có thể viết hơn có thể quan sát những gì được nối thêm sau một danh sách vô hạn.