recursion - 如何在 OCaml 中生成递归列表

Question

我想实现 Haskellcycle函数的模拟。

如果我明确传递列表元素，这似乎微不足道：

let cycle a b c =
  let rec l = a::b::c::l in
  l

cycle 1 2 3生成递归列表1, 2, 3, 1...

但是，如何在另一个常规列表的基础上生成递归列表？

let cycle lst = ...

用法

cycle [1;2;3]

Answer 1

在像 ML 这样的热切语言中，您需要使用流。例如

# let cycle = Stream.from (fun n -> Some (List.nth [1;2;3] (n mod 3)));;
val cycle : int Stream.t = <abstr>
# Stream.npeek 10 cycle;;
- : int list = [1; 2; 3; 1; 2; 3; 1; 2; 3; 1]

Answer 2

似乎制作这种递归列表的唯一方法是使用Obj模块。

复制列表并使其递归

let cycle lst = match lst with
  | [] -> []
  | _ ->
    let rec get_last_cell = function
      | [] -> assert false
      | _::[] as last -> last
      | _::tl -> (get_last_cell tl)
    in
    let new_lst = List.map (fun x -> x) lst in
    let last_cell = get_last_cell new_lst in
    Obj.set_field (Obj.repr last_cell) 1 (Obj.repr new_lst);
    new_lst

创建递归列表，然后插入新的 cons 单元格

let cycle lst = match lst with
  | [] -> []
  | hd::tl ->
      let rec loop cell lst =
        match lst with
        | [] -> ()
        | hd::tl ->
            let new_cell = [hd] in
            let new_cell_obj = Obj.repr new_cell in
            let cell_obj = Obj.repr cell in
            Obj.set_field new_cell_obj 1 (Obj.field cell_obj 1);
            Obj.set_field cell_obj 1 new_cell_obj;
            loop new_cell tl
      in
      let rec cyc_lst = hd::cyc_lst in
      loop cyc_lst tl;
      cyc_lst

这个想法很简单：

1. cyc_lst创建只有一个元素的递归列表。
2. 在 tail of 之前插入一个或多个新的 cons 单元格cyc_lst。

例子

cycle [1;2]

1. 创建递归列表cyc_lst。它在内存中表示为一个自递归的 cons 单元

   让 rec cyc_lst = hd::cyc_lst
   
   .--------。
   | |
   | +---+-|-+
   `->| 1 | * |
      +---+---+
   

2. new_cell使用 2 作为唯一元素创建

   让 new_cell = [高清]
   
      细胞新细胞
   .--------。
   | |
   | +---+-|-+ +---+---+
   `->| 1 | * | | 2 | X |
      +---+---+ +---+---+
   

3. 将new_cell尾指针设置为第一个单元格

   Obj.set_field new_cell_obj 1 (Obj.field cell_obj 1)
   
      细胞新细胞
   .--------.--------------。
   | | |
   | +---+-|-+ +---+-|-+
   `->| 1 | * | | 2 | * |
      +---+---+ +---+---+
   

4. 将cell尾指针设置为new_cell

   obj.set_field cell_obj 1 new_cell_obj
   
      细胞新细胞
   .------------------------。
   | |
   | +---+---+ +---+-|-+
   `->| 1 | *------->| 2 | * |
      +---+---+ +---+---+
   

我希望 GC 可以接受这样的列表操作。如果不是，请告诉我。

Answer 3

据我所知，OCaml 不适合这种编码，除非你想深入到语言的不安全部分。

坚持语言的安全部分（但使用第 7 章中的扩展），这里有一个（不是很令人印象深刻）版本cycle，适用于长度为 3 的列表：

let cycle = function
    | [] -> []
    | [x] -> let rec res = x :: res in res
    | [x; y] -> let rec res = x :: q and q = y :: res in res
    | [x; y; z] -> let rec res = x :: t and t = y :: v and v = z :: res in res
    | _ -> failwith "list too long"

很容易看出如何将其扩展到任何所需的固定长度，而不是任意长度。

这是该功能的会话：

# #use "cyc.ml";;
val cycle : 'a list -> 'a list = <fun>
# cycle [1;2;3];;
- : int list =
[1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1;
 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2;
 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3;
 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1;
 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2;
 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; ...]

这是我能做的最好的，无论如何。我希望它会有所帮助。

Answer 4

你也可以像这样定义它

# let cycle items =
    let buf = ref [] in
    let rec next i =
      if !buf = [] then buf := items;
      match !buf with
        | h :: t -> (buf := t; Some h)
        | [] -> None in
    Stream.from next;;
val cycle : 'a list -> 'a Stream.t = <fun>

utop # let test = cycle [1; 2; 3];;
val test : int Stream.t = <abstr> 
utop # Stream.npeek 10 test;;
- : int list = [1; 2; 3; 1; 2; 3; 1; 2; 3; 1]

这是来自：

http://ocaml.org/tutorials/streams.html

Answer 5

您需要另一个答案中的流或惰性列表：

type 'a llist = LNil | LCons of 'a * 'a llist Lazy.t
let cycle = function
| [] -> invalid_arg "cycle: empty list"
| hd::tl ->
  let rec result =
    LCons (hd, lazy (aux tl))
  and aux = function
    | [] -> result
    | x::xs -> LCons (x, lazy (aux xs)) in
  result