OCAML 목록 : 부록 및 맵 기능을 구현합니다

Question

저는 현재 친구의 OCAML 프로그램을 확장하려고합니다. 일부 데이터 분석에 필요한 엄청난 기능 모음입니다. 실제로 OCAML 균열이 아니기 때문에 현재 (나를 위해) 이상한 목록 구현에 갇혀 있습니다.

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

나는 이것이 일종의 "게으른"목록을 구현한다는 것을 알았지 만 그것이 실제로 어떻게 작동하는지 전혀 모른다. 위의 유형을 기반으로 부록 및 맵 함수를 구현해야합니다. 아무도 어떻게 해야할지 아이디어를 얻었습니까?

모든 도움이 정말 감사하겠습니다!

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를 통해 함수 (기술 용어는 폐쇄)에 캡슐화된다는 것입니다. 그런 다음 표현식 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

즉, 게으른 세포 값.

맵 구현은 위의 정의 측면에서 더 의미가있을 수 있습니다.

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

Append와 마찬가지로

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

becomes

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 표현식의 값을 계산합니다 정확히 한 번.

Answer 3

예, 목록은 무한 할 수 있습니다. 다른 답변에 주어진 코드는 무한 목록의 끝에 추가되지만 무한 목록에 따라 추가 된 내용을 관찰 할 수있는 것보다 쓸 수있는 프로그램은 없습니다.