4

假设我有以下 OCaml 代码块：

let genblocks () =
  let blocks = ref [] in
  let rec loop depth block =
    let iter i = loop (depth - 1) (i :: block) in
    match depth with
      | 0 -> blocks := block :: !blocks
      | _ -> List.iter iter [1;2;3;4]
  in
  loop 4 [];
  !blocks

这会生成一个列表列表：[[1;1;1;1]; [1;1;1;2]; ...; [4;4;4;4]]。

现在，我想将其转换为流（使用Stream模块或类似的东西）。但是，我不知道如何在保持当前代码的整体递归结构的同时做到这一点。我想保持这种结构的原因是它使我能够在生成过程中轻松地删除包含某些属性的列表。例如，使用这种代码结构，在生成过程中，我可以轻松地删除包含 sublist 的列表[1;1]。（以上只是一个玩具示例，我的实际应用更复杂......）。

关于如何将上述代码转换为“流”实例的任何提示/想法/指针？一旦达到零深度，我就无法“回溯”......

编辑：另一种看待问题的方式：有没有办法进行转换genblocks以摆脱列表引用？这似乎是使其与流兼容所需的第一步。

谢谢。

4

3 回答 3

3

我的回答中有三点不同：

  1. 演示摆脱可变变量的通用技术

  2. 一种特定于算法的技术，可以很容易地生成流

  3. 指向通用技术的链接，可将任何生产者转变为点播流

首先，让我们在枚举的基础上使您的算法通用：

let genblocks n =
  (* base = [1; ... ; n] *)
  let base = Array.to_list (Array.init n (fun i -> i+1)) in
  let blocks = ref [] in
  let rec loop depth block =
    let iter i = loop (depth - 1) (i :: block) in
    match depth with
      | 0 -> blocks := block :: !blocks
      | _ -> List.iter iter base
  in
  loop n [];
  !blocks

现在不看代码做了什么，有一个非常简单的方法可以摆脱枚举：将任何A -> B 使用可变类型的类型C函数转换为A * C -> B * C接收状态的类型函数，并返回其修改后的值——这就是所谓的“状态单子”。blocks因此，我将简单地为您的函数添加一个附加参数loopand iter，并使其返回 not unitbut int list list：

let genblocks n =
  let base = Array.to_list (Array.init n (fun i -> i+1)) in
  let rec loop depth blocks block =
    let iter blocks i = loop (depth - 1) blocks (i :: block) in
    match depth with
      | 0 -> block :: blocks
      | _ -> List.fold_left iter blocks base
  in
  loop n [] []

现在让我们看看这个算法究竟做了什么：

# genblocks 3;;
- : int list list =
[[3; 3; 3]; [2; 3; 3]; [1; 3; 3]; [3; 2; 3]; [2; 2; 3]; [1; 2; 3]; [3; 1; 3];
 [2; 1; 3]; [1; 1; 3]; [3; 3; 2]; [2; 3; 2]; [1; 3; 2]; [3; 2; 2]; [2; 2; 2];
 [1; 2; 2]; [3; 1; 2]; [2; 1; 2]; [1; 1; 2]; [3; 3; 1]; [2; 3; 1]; [1; 3; 1];
 [3; 2; 1]; [2; 2; 1]; [1; 2; 1]; [3; 1; 1]; [2; 1; 1]; [1; 1; 1]]

当使用参数 3 调用时（在您的代码中 4 是硬编码的），此算法返回数字 1、2 和 3 的所有 3 组合。否则，它会枚举以 3 为底的计数系统中的所有三位数（使用 1 和 3 之间的数字，而不是像往常一样使用 0 和 2）。

有一种非常简单的方法可以枚举你在学校学到的数字：从一个数字到下一个数字，只需增加（或减少）它。在您的情况下，列表以“大”数字开始并进入“小”数字，因此我们将递减。事实上，你的基地是 [1; N] 而不是 [0; N-1]，递减函数写成

let decr n block =
  let rec decr n = function
    | [] -> raise Exit
    | 1::rest -> n :: decr n rest
    | i::rest -> (i - 1) :: rest
  in try Some (decr n block) with Exit -> None

当我们达到 0 时（在您的系统中，[1;1;1..]），我让它返回 None，以便在此时轻松停止枚举。

decr 3 [3;3;3];;
- : int list option = Some [2; 3; 3]
# decr 3 [1;2;3];;
- : int list option = Some [3; 1; 3]
# decr 3 [1;1;1];;
- : int list option = None

从这个函数中枚举所有数字是微不足道的：

let start n = Array.to_list (Array.make n n)

let genblocks n =
  let rec gen = function
    | None -> []
    | Some curr -> curr :: gen (decr n curr)
  in gen (Some (start n))

但重要的一点是，生成的整个状态仅存储在一个值中，即当前数字。所以你可以很容易地把它变成一个流：

let genblocks n =
  let curr = ref (Some (start n)) in
  Stream.from (fun _ ->
    match !curr with
      | None -> None
      | Some block ->
        curr := (decr n block);
        Some block
  )

# Stream.npeek 100 (genblocks 3);;
- : int list list =
[[3; 3; 3]; [2; 3; 3]; [1; 3; 3]; [3; 2; 3]; [2; 2; 3]; [1; 2; 3]; [3; 1; 3];
 [2; 1; 3]; [1; 1; 3]; [3; 3; 2]; [2; 3; 2]; [1; 3; 2]; [3; 2; 2]; [2; 2; 2];
 [1; 2; 2]; [3; 1; 2]; [2; 1; 2]; [1; 1; 2]; [3; 3; 1]; [2; 3; 1]; [1; 3; 1];
 [3; 2; 1]; [2; 2; 1]; [1; 2; 1]; [3; 1; 1]; [2; 1; 1]; [1; 1; 1]]

是否有一种通用的方法可以将生产者驱动的函数（根据问题以最自然的节奏累积项目）转换为消费者驱动的函数（由消费者决定一次产生一个元素）？是的，我在以下博客文章中对此进行了解释：

生成器、迭代器、控制和延续

最重要的想法是，您可以通过对代码进行机械但复杂的转换，明确生产者的“上下文”是什么，他的当前状态是什么，编码为复杂的值和控制流（调用已经制作，此时您在哪个条件分支中）。然后将此上下文转换为一个值，您可以将其用作此处使用的“数字”来派生消费者驱动的流。

于 2013-04-17T06:26:48.760 回答
2

假设此代码不是家庭作业，那么您几乎可以通过使用电池Enum中的模块来翻译您的代码以逐字返回“流” 。即函数和。您可能已经注意到，OCaml 附带的流模块非常小。最好使用替代方案。Enum.pushEnum.empty

于 2013-04-16T02:25:08.537 回答
0

我遇到了和你类似的问题，所以我开发了一个迭代器模块（它绝对不是新的，但我无法找到一个做同样事情的简单包）

这是一个链接：https ://github.com/JoanThibault/DAGaml/blob/master/tools/iter.mli

使用此模块，您可以重新编写代码

open IterExtra (* add some handy symbols to manipulate iterators *)
let genblock n = (Iter.range 1 (4+1)) $^ n
val genblock : int -> int list Iter.iter

现在，如果您想使用某些功能对其进行过滤prune : int list -> bool：

let genblock n = (Iter.range 1 (4+1)) $^ n |> Iter.filter prune
val genblock : int -> int list Iter.iter

最后，您可以使用一些打印功能迭代您的迭代器print : int list -> unit：

let n = 10;;
Iter.iter print (genblock n);;
于 2017-04-18T15:28:20.650 回答