4

我一直在研究一个单独的函数，该函数返回一个列表，该列表在列表 l 的每个 k 元素之后插入元素 x （从列表末尾开始计数）。例如，单独的 (1, 0, [1,2,3,4]) 应该返回 [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 来简化函数，但我似乎无法让它正常工作。关于如何解决这个问题的任何提示/建议？谢谢你！

4

1 回答 1

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的副本，每次它达到 0 时逐渐递减并重置。因此，虽然吐出的列表相当于折叠的累积变量，但临时累积（偶尔重置）以几乎相同的方式。kikkinserti

  • 更改kinsert的累积变量以腾出空间i：

    fun separate (k, x, L) =
    let fun kinsert (y, (i, xs)) = ...
    in foldr kinsert (?, []) L
    end

    现在 fold 的结果变成了'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版本偏离了 fold 以一种方式执行的递归模式：在中间模式中，当imatches时0，您不会将元素切掉ls，否则 fold 会迫使您这样做。因此，您的0案例看起来与原始案例略有不同；你可能会遇到一个错误的错误。

  • 请记住，foldr实际上首先访问列表中的最后一个元素，此时i将具有其初始值，其中 originalkinsert的初始值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]。

于 2018-03-08T10:26:42.097 回答