gpt4 book ai didi

sml - 使用 foldl/foldr 插入函数

转载 作者:行者123 更新时间:2023-12-04 23:21:55 25 4
gpt4 key购买 nike

我一直在研究一个单独的函数,该函数返回一个列表,该列表在列表 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 来简化函数,但我似乎无法让它正常工作。关于如何解决这个问题的任何提示/建议?谢谢你!

最佳答案

这些或多或少是我尝试使用 foldl 编写函数时的想法。/foldr :

  • foldl/foldr从组成最终结果的逻辑中抽象出列表递归。
  • 首先勾勒出一个与原始程序结构非常相似的函数,但其​​中 foldr使用和 kinsertfoldr 的函数不是递归函数:
    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 shell 看起来与原来的略有不同;您可能会遇到逐一错误。
  • 请记住 foldr实际上首先访问列表中的最后一个元素,此时 i将有其初始值,其中与原始 kinsert , i 的初始值当你在第一个元素时。
  • 取决于您是否使用 foldlfoldr你会遇到不同的问题: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] .
  • 关于sml - 使用 foldl/foldr 插入函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49163757/

    25 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com