SML中如何将常规seq转换为biseq？

问题背景 #

用户定义了两种序列数据类型：

双向序列（biseq） #

datatype direction = Back | Forward; 
datatype 'a biseq =   bNil 
                    | bCons of 'a * (direction -> 'a biseq);

常规单向序列（seq） #

datatype 'a seq = Nil | Cons of 'a * (unit -> 'a seq);

用户尝试编写转换函数将seq转为biseq，代码如下：

fun new Nil = bNil
  | new (Cons (x, xf)) =
    bCons (x, fn direction => new (xf ()));

该函数无法正常工作，核心原因是单向序列seq仅能向前获取下一个元素，没有记录前序节点的信息，导致转换后的biseq无法响应Back方向的遍历请求。

解决方案 #

要实现正确转换，需要在构建biseq时同步维护当前节点的前序信息。由于原序列是单向的，我们只能在遍历过程中记录已走过的节点，以此支持回溯操作。

通过辅助函数实现，该函数同时接收当前处理的单向序列和已遍历元素的列表（作为前序节点来源）：

fun seq_to_biseq_helper Nil _ = bNil
  | seq_to_biseq_helper (Cons(x, xf)) prev =
    bCons(x, fn
        Forward => seq_to_biseq_helper (xf()) (x :: prev)
      | Back => case prev of
                   [] => bNil  // 处于首节点，无前置元素
                 | y :: ys => seq_to_biseq_helper (Cons(y, fn () => seq_to_biseq_from_list ys)) ys
    )
and seq_to_biseq_from_list [] = Nil
  | seq_to_biseq_from_list (h :: t) = Cons(h, fn () => seq_to_biseq_from_list t);

// 对外暴露的转换入口函数，初始前序列表为空
fun seq_to_biseq s = seq_to_biseq_helper s [];

逻辑说明 #

• Forward方向处理：继续遍历原单向序列，同时将当前元素加入前序列表，让后续节点可以通过该列表回溯到当前节点。
• Back方向处理：将前序列表的首个元素作为新的当前节点，把剩余前序元素重新构建为单向序列，作为新节点的Forward指向（回到之前的当前节点），以此实现双向遍历的闭环。

内容的提问来源于stack exchange，提问作者Maya