假设我有以下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模块或类似的东西)。但是，我不知道如何在保持当前代码的整体递归结构的同时做到这一点。我想要维护这个结构的原因是，它使我能够在生成过程中轻松地删除包含某些属性的列表。例如，使用这种代码结构，在生成过程中，我可以很容易地删除包含子列表[1;1]的列表。(以上只是一个简单的例子，我的实际应用要复杂得多…)
关于如何将上述代码转换为"流"实例的任何提示/想法/指针?一旦深度为0，我就无法"回溯"了…
edit:另一种看待问题的方式:是否有方法转换genblocks以摆脱列表引用?这似乎是使它与流兼容所需要的第一步。
谢谢。
在我的回答中有三个不同的东西:
-
一个通用技术的演示来摆脱你的可变变量
-
一种特定于算法的技术，可以很容易地生成一个流
-
一个通用技术的链接，可以将任何生产者变成点播流
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类型的函数中，该函数接收状态，并返回其修改后的值——这就是所谓的"状态单子"。所以我只要加上an为函数loop和iter添加参数blocks，以及使它返回int list list而不是unit:
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]]
时(在代码中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]]
是否有一种通用的方法来转换生产者驱动的函数(即按最自然的节奏堆积物品)问题)转化为消费者驱动的功能(即产生元素1)在当时，什么时候由消费者决定?是的，我用下面的博文:
生成器、迭代器、控件和延续
重要的想法是，你可以通过机制但复杂的转换在你的代码中，明确生产者的"上下文"是什么，他现在的状态是什么，就像编码成一个复杂混乱的价值观和控制流(已经进行了哪些调用，在哪些条件分支中你在这一点上吗?然后将此上下文转换为值，即你可以使用这里使用的"数字"来推导消费者驱动的流。
假设这段代码不是家庭作业，那么您几乎可以通过使用电池中的Enum模块将代码逐字翻译为返回"流"。即函数Enum.push和Enum.empty。您可能已经注意到，OCaml附带的流模块非常小。
我有一个类似的问题，所以我开发了一个迭代器模块(它肯定不是新的，但我不能找到一个简单的包，做同样的事情)
链接: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);;