假设我有以下 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] 的列表。 (以上只是一个玩具示例,我的实际应用更复杂......)。

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

编辑: 另一种看待问题的方式:有没有办法转换 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 类型的函数中,该函数接收状态,并返回其修改后的值——
    这就是所谓的“状态单子(monad)”。所以我会简单地添加一个
    函数 blocksloop 的附加参数 iter ,以及
    让它不返回 unit 而是返回 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 为基数的数字系统(使用 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 时,我让它返回 None(在你的系统中,[1;1;1..])到
    在这一点上轻松停止枚举。
    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]]
    

    有没有通用的方法来转换生产者驱动的功能
    (根据最自然的节奏积累项目
    问题)转化为消费者驱动的功能(即生产要素一
    当时,何时由消费者决定)?是的,我在
    以下博客文章:

    Generators, iterators, control and continuations

    重要的想法是,您可以通过机械但复杂的转换
    在您的代码中,明确生产者的“上下文”是什么,
    他目前的状态,编码为一团复杂的值(value)观和
    控制流(进行了哪些调用,在哪个条件分支中
    你在这一点上)。然后将此上下文转换为一个值,即
    您可以使用这里使用的“数字”来推导出消费者驱动的
    溪流。

    关于stream - 将 ocaml 函数转换为流,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/16027627/

    10-11 22:54
    查看更多