使用 foldl/foldr 插入函数

Question

我一直在研究一个单独的函数，该函数 return 是一个列表，它在列表 l 的每个 k 元素之后插入元素 x（从列表的末尾）。例如，单独的 (1, 0, [1,2,3,4]) 应该 return [1,0,2,0,3,0,4]。我完成了该功能并使其按如下方式工作：

fun separate (k: int, x: 'a, l: 'a list) : 'a list = 
  let
    fun kinsert [] _ = []
      | kinsert ls 0 = x::(kinsert ls k)
      | kinsert (l::ls) i = l::(kinsert ls (i-1))
  in
     List.rev (kinsert (List.rev l) k)
  end

我现在尝试使用 foldl/foldr 来简化函数而不使用任何递归，但我似乎无法让它正常工作。 tips/suggestions 关于如何解决这个问题？谢谢你！

Answer 1

这些或多或少是我在尝试使用 foldl/foldr:

编写函数时的想法

foldl/foldr 从构成最终结果的逻辑中抽象出列表递归。
首先草拟一个函数，该函数与您的原始程序具有非常相似的结构，但是使用 foldr 并且 kinsert 而不是递归函数是赋予 foldr 的功能：
```
fun separate (k, x, L) =
    let fun kinsert (y, ys) = ...
    in foldr kinsert [] L
    end
```
这不是绝对必要的； kinsert 还不如匿名。
您正在使用内部辅助函数 kinsert，因为您需要 k (i) 的副本，您逐渐递减并重置为 k每次到0。所以虽然kinsert吐出的列表相当于折叠的累积变量，i是暂时累积（偶尔重置）以几乎相同的方式。
更改kinsert的累加变量为i腾出空间:
```
fun separate (k, x, L) =
    let fun kinsert (y, (i, xs)) = ...
    in foldr kinsert (?, []) L
    end
```
现在折叠的结果变成了'a * 'a list，这导致了两个问题：1）我们真的只是想暂时累积i，但是它最终结果的一部分。这可以通过使用 #2 (foldr ...) 丢弃它来规避。 2) 如果结果现在是一个元组，我不确定用第一个 i 代替 ?.

由于kinsert是单独的函数声明，可以使用模式匹配和多个函数体：

fun separate (k, x, L) =
    let fun kinsert (y, (0, ys)) = ...
          | kinsert (y, (i, ys)) = ...
    in ... foldr kinsert ... L
    end

你原来的kinsert以一种方式偏离了折叠执行的递归模式：在中间模式中，当i匹配0时，你'不要砍掉 ls 的元素，否则折叠会迫使您这样做。所以你的 0 案例看起来会与原来的案例略有不同；你可能会运行进入 off-by-one 错误。
记住 foldr 实际上首先访问列表中的最后一个元素，此时 i 将具有其初始值，而原始 kinsert ，i 的初始值将是您位于第一个元素时的值。
根据您使用的是 foldl 还是 foldr，您会运行遇到不同的问题：foldl 会颠倒您的列表，但地址正确顺序的项目。 foldr 将保持列表顺序正确，但当 k 不划分 L 的长度时会产生不同的结果...

此时，考虑使用foldl并反转列表：

fun separate (k, x, L) =
    let fun kinsert (y, (?, ys)) = ...
          | kinsert (y, (i, ys)) = ...
    in rev (... foldl kinsert ... L)
    end

否则你会开始注意到 separate (2, 0, [1,2,3,4,5]) 应该给出 [1,2,0,3,4,0,5] 而不是 [1,0,2,3,0,5].

使用 foldl/foldr 插入函数

Insert function using foldl/foldr

sml

ml

mosml