如何在OCaml中生成递归列表 [英] How to generate recursive list in OCaml

问题描述

我想实现Ha​​skell cycle函数的模拟.

I would like to implement analog of Haskell cycle function.

如果我明确地传递列表元素，那似乎是微不足道的:

If I pass list elements explicitly it seems trivial:

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

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

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

But, how to generate recursive list on basis of another regular list?

let cycle lst = ...

用法

cycle [1;2;3]

推荐答案

制作此类递归列表的唯一方法似乎是使用Obj模块.

It seems the only way to make such recursive list is by using Obj module.

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

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

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. 在cyc_lst尾部之前立即插入一个或多个新的cons细胞.

1. Create recursive list cyc_lst with only one element.
2. Insert one or more new cons cells immediately before tail of cyc_lst.

示例

cycle [1;2]

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

1. Create recursive list cyc_lst. It is represented in memory as a self-recursive cons cell

let rec cyc_lst = hd::cyc_lst

.--------.
|        | 
|  +---+-|-+
`->| 1 | * |
   +---+---+

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

let new_cell = [hd]

   cell            new_cell
.--------.
|        |
|  +---+-|-+      +---+---+
`->| 1 | * |      | 2 | X |
   +---+---+      +---+---+

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

Set new_cell tail pointer to first cell

Obj.set_field new_cell_obj 1 (Obj.field cell_obj 1)

   cell            new_cell
.--------.--------------.
|        |              |
|  +---+-|-+      +---+-|-+
`->| 1 | * |      | 2 | * |
   +---+---+      +---+---+

将cell尾指针设置为new_cell

Set cell tail pointer to new_cell

Obj.set_field cell_obj 1 new_cell_obj

   cell            new_cell
.-----------------------.
|                       |
|  +---+---+      +---+-|-+
`->| 1 | *------->| 2 | * |
   +---+---+      +---+---+

我希望GC可以使用此类列表操作.让我知道是否可以.

I hope GC is ok with such list manipulations. Let me know if it is not.

这篇关于如何在OCaml中生成递归列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！