如何在Haskell中使用foldr实现删除-Java 学习之路

这几天我一直在学习折叠 . 我可以用它们实现简单的函数，比如 length ， concat 和 filter . 我所坚持的是试图用 delete ， take 和 find 这样的 foldr 函数来实现 . 我用显式递归实现了这些，但对我来说，如何将这些类型的函数转换为右折叠似乎并不明显 .

我研究了Graham Hutton和Bernie Pope的教程 . 模仿Hutton的 dropWhile ，我能够用 foldr 实现 delete 但它在无限列表上失败了 .

从阅读Implement insert in haskell with foldr，How can this function be written using foldr?和Implementing take using foldr，似乎我需要使用 foldr 生成一个函数，然后执行某些操作 . 但我不知道如何以这种方式实现例如 delete .

您能否向我解释一下使用 foldr 懒惰版本的函数实现的一般策略，就像我提到的那样 . 也许您也可以实现 delete 作为示例，因为这可能是最简单的一个 .

我正在寻找一个初学者可以理解的详细解释 . 我对解决方案不感兴趣，我想发展一种理解，所以我可以自己提出类似问题的解决方案 .

谢谢 .

Edit: 在撰写本文时，有一个有用的答案，但它对使用foldr生成函数的方法更感兴趣，然后该函数执行某些操作 . 我的问题中的链接都有这样的例子 . 我不太了解这些解决方案，所以我希望获得有关此方法的更多信息 .

3 回答

1
delete 是模态搜索 . 它有两种不同的操作模式 - 无论是否已经找到结果 . 您可以使用 foldr 构造一个函数，在检查每个元素时将状态传递给该行 . 所以在 delete 的情况下，状态可以是一个简单的 Bool . 它不是最好的类型，但它会做 .

确定状态类型后，即可开始处理 foldr 构造 . 我'm going to walk through figuring it out the way I did. I'将启用 ScopedTypeVariables ，这样我就可以更好地注释子表达式的类型 . 你知道状态类型，你知道你希望 foldr 生成一个取该类型值的函数，并返回所需最终类型的值 . 这足以开始绘制草图 .
```
{-# LANGUAGE ScopedTypeVariables #-}

delete :: forall a. Eq a => a -> [a] -> [a]
delete a xs = foldr f undefined xs undefined
  where
    f :: a -> (Bool -> [a]) -> (Bool -> [a])
    f x g = undefined
```
这是一个开始 . g 的确切含义在这里有点棘手 . 事实上，将其视为延续是准确的 . 它绝对代表执行折叠的其余部分，以及您选择传递的任何状态 . 鉴于此，是时候弄清楚要放在哪些地方了 .
```
{-# LANGUAGE ScopedTypeVariables #-}

delete :: forall a. Eq a => a -> [a] -> [a]
delete a xs = foldr f undefined xs undefined
  where
    f :: a -> (Bool -> [a]) -> (Bool -> [a])
    f x g found | x == a && not found = g True
                | otherwise           = x : g found
```
这似乎相对简单 . 如果当前元素是正在搜索的元素，并且它没有't yet been found, don' t输出它，并继续将状态设置为 True ，表示已找到它 . otherwise ，输出当前值并继续当前状态 . 这只是将其余参数留给 foldr . 最后一个是初始状态 . 另一个是空列表的状态函数 . 好吧，那些也不是太糟糕 .
```
{-# LANGUAGE ScopedTypeVariables #-}

delete :: forall a. Eq a => a -> [a] -> [a]
delete a xs = foldr f (const []) xs False
  where
    f :: a -> (Bool -> [a]) -> (Bool -> [a])
    f x g found | x == a && not found = g True
                | otherwise           = x : g found
```
无论状态如何，在遇到空列表时都会生成一个空列表 . 初始状态是尚未找到要搜索的元素 .

该技术也适用于其他情况 . 例如， foldl 可以用这种方式写成 foldr . 如果将 foldl 视为重复转换初始累加器的函数，您可以猜测正在生成的函数 - 如何转换初始值 .
```
{-# LANGUAGE ScopedTypeVariables #-}

foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a
foldl f z xs = foldr g id xs z
  where
    g :: b -> (a -> a) -> (a -> a)
    g x cont acc = undefined
```
当问题被定义为操纵初始累加器（名为 z ）时，基本情况并不太难以找到 . 空列表是标识转换 id ，传递给创建函数的值是 z .

g 的实现比较棘手 . 它可以足够了，你需要考虑可用功能的含义 .

让我们从看起来应该使用的值及其类型的清单开始 . 看起来他们必须在 g 的正文中使用的东西是 f :: a -> b -> a ， x :: b ， cont :: (a -> a) 和 acc :: a . f 显然会将 x 作为其第二个参数，但是有一个问题是适当的地方使用 cont . 要弄清楚它的去向，请记住它表示通过处理列表的其余部分返回的转换函数，并且 foldl 处理当前元素，然后将该处理的结果传递给列表的其余部分 .
```
{-# LANGUAGE ScopedTypeVariables #-}

foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a
foldl f z xs = foldr g id xs z
  where
    g :: b -> (a -> a) -> (a -> a)
    g x cont acc = cont $ f acc x
```
这也表明 foldl' 可以用这种方式编写，只有一个微小的变化：
```
{-# LANGUAGE ScopedTypeVariables #-}

foldl' :: forall a b. (a -> b -> a) -> a -> [b] -> a
foldl' f z xs = foldr g id xs z
  where
    g :: b -> (a -> a) -> (a -> a)
    g x cont acc = cont $! f acc x
```
区别在于 ($!) 用于建议 f acc x 在传递给 cont 之前的评估 . （我说"suggest"因为有一些边缘情况，即使是WHNF， ($!) 也不会强制进行评估 . ）
回复于 2024-05-07T08:12:54+08:00
11
delete 没有't operate on the entire list evenly. The structure of the computation isn' t一次只考虑整个列表中的一个元素 . 它在点击元素后会有所不同，它实现为 foldr . 必须进行某种后处理 .

当发生这种情况时，一般模式是你构建一对值，并在完成 foldr 时只取一个值 . 那个's probably what you did when you imitated Hutton' s dropWhile ，虽然我包括代码 . 像这样的东西？
```
delete :: Eq a => a -> [a] -> [a]
delete a = snd . foldr (\x (xs1, xs2) -> if x == a then (x:xs1, xs1) else (x:xs1, x:xs2)) ([], [])
```
主要的想法是 xs1 总是会成为列表的完整尾部， xs2 是 delete 在列表尾部的结果 . 由于您只想删除匹配的第一个元素，因此当您匹配're searching for, you just want to return the rest of the list unchanged - which fortunately is what'始终位于 xs1 中的值时，您不希望在尾部使用 delete 的结果 .

是的，这不适用于无限列表 - 但仅限于一个非常具体的原因 . lambda太严格了 . foldr 仅适用于无限列表，当它提供的函数并不总是强制求解其第二个参数时，并且该lambda总是强制在该对的模式匹配中评估其第二个参数 . 切换到无可辩驳的模式匹配修复了这一点，通过允许lambda在检查其第二个参数之前生成构造函数 .
```
delete :: Eq a => a -> [a] -> [a]
delete a = snd . foldr (\x ~(xs1, xs2) -> if x == a then (x:xs1, xs1) else (x:xs1, x:xs2)) ([], [])
```
这不是获得结果的唯一方法 . 使用let-binding或 fst 和 snd 作为元组的访问器也可以完成这项工作 . 但它是最小差异的变化 .

这里最重要的一点是要非常小心处理传递给 foldr 的reduce函数的第二个参数 . 您希望尽可能推迟检查第二个参数，以便 foldr 可以在尽可能多的情况下延迟流式传输 .

如果你查看那个lambda，你会看到在使用reduce函数的第二个参数做任何事情之前选择了分支 . 此外，您将看到大多数情况下，reduce函数在结果元组的两半之前生成一个列表构造函数，然后才需要计算第二个参数 . 由于这些列表构造函数是 delete 的原因所在，因此它们对于流式传输非常重要 - 只要你不让它们阻挡它们 . 并且在对无关可变的情况下进行模式匹配就是让它不受影响的原因 .

作为 foldr 的流媒体属性的奖励示例，请考虑我最喜欢的示例：
```
dropWhileEnd :: (a -> Bool) -> [a] -> [a]
dropWhileEnd p = foldr (\x xs -> if p x && null xs then [] else x:xs) []
```
它流动 - 尽可能多 . 如果你确切地知道它的确实时间和原因，并且几乎不了解 foldr 的流结构的每个细节 .
回复于 2024-05-07T08:12:54+08:00

这是一个简单的删除，用foldr实现：

delete :: (Eq a) => a -> [a] -> [a]
delete a xs = foldr (\x xs -> if x == a then (xs) else (x:xs)) [] xs

回复于 2024-05-07T08:12:54+08:00

如何在Haskell中使用foldr实现删除

3 回答

相关问题