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

Question

我已经学习了几天的折叠函数。我可以使用简单的函数，例如length，concat和filter。我遇到的问题是尝试使用foldr实现delete，take和find等函数。我已经使用显式递归来实现了这些函数，但我不知道如何将这些类型的函数转换为右折叠。

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

从阅读使用foldr实现Haskell中的插入，如何使用foldr编写此函数？和使用foldr实现take，似乎我需要使用foldr生成一个然后执行某些操作的函数。但我不真正理解这些解决方案，也不知道如何以这种方式实现delete。

您能否向我解释一种使用foldr实现惰性函数的通用策略，例如我提到的那些函数。也许您还可以作为示例实现delete，因为这可能是最简单的之一。

我正在寻找一个初学者可以理解的详细说明。我不只是希望得到解决方案，我希望获得理解，以便自己针对类似的问题提出解决方案。

谢谢。

编辑：撰写本文时，有一个有用的答案，但它并不完全符合我的要求。我更感兴趣的是使用foldr生成函数的方法，然后执行某些操作。我的问题中的链接提供了这样的示例。我不太理解这些解决方案，因此希望了解更多关于这种方法的信息。

- user168064

Answer 1

delete是一种模态搜索。它有两种不同的操作模式 - 是否已经找到结果。您可以使用foldr构造一个函数，将状态作为每个元素被检查时向下传递。因此，在delete的情况下，状态可以是一个简单的Bool。虽然它不是最好的类型，但愿意依旧可行。

一旦确定了状态类型，就可以开始对foldr进行构建。我将按照我自己的方式来解释如何完成这个过程。为了更好地注释子表达式的类型，我将启用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的确切含义有点棘手。实际上，它是处理列表其余部分的函数。事实上，把它看作是一个续集是准确的。它绝对代表执行剩下的折叠，带着你选择传递的任何状态。鉴于此，现在是时候想出在某些 undefined 位置放什么了。

{-# 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

看起来相对简单。如果当前元素是要搜索的元素，并且它尚未被找到，则不输出它，并继续将状态设置为True，表示已经找到。否则，输出当前值并继续使用当前状态。这只是让 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之前对其进行求值。(我说“建议”是因为有一些边缘情况，其中($!)甚至不会强制执行到WHNF。)

- Carl

Answer 2

delete不能均匀地作用于整个列表。计算的结构不仅考虑了一个元素，而是在找到目标元素后发生了改变。这告诉您它不能仅实现为一个foldr。将需要某种后处理。

当发生这种情况时，一般的模式是建立一对值，并仅在foldr完成时取其中之一。这可能就是您在模仿Hutton的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的结果。由于您只想删除与之匹配的第一个元素，因此在匹配所寻找的值时，不要使用delete的结果来操作列表尾部，只需返回列表的其余部分即可 - 幸运的是这正是xs1中始终存在的内容。

但是，这在无限列表上不起作用-仅有一个非常特定的原因。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绑定或在元组上使用fst和snd作为访问器也可以完成工作。但这是差异最小的更改。

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

如果您查看lambda，您会发现在对减少函数的第二个参数执行任何操作之前选择了要采取的分支。此外，您会发现大多数情况下，减少函数在需要评估第二个参数之前就在结果元组的两半中产生列表构造器。由于这些列表构造器是从delete中获取的，因此它们对于流式传输很重要-只要您不让配对干扰即可。将模式匹配设置为不可否认是使其不受干扰的原因。

作为 foldr 流属性的奖励示例，请考虑我的最爱示例：

dropWhileEnd :: (a -> Bool) -> [a] -> [a]
dropWhileEnd p = foldr (\x xs -> if p x && null xs then [] else x:xs) []

它会尽可能地进行流式处理。如果你能确定它何时以及为什么会或不会进行流式处理，那么你就几乎理解了 foldr 的所有流式处理结构细节。

- Carl

---

我很感激你的回答并且觉得它很有用。如果我有足够的声望，我会点赞的，但是我还没有接受你的回答，因为它不完全符合我的要求。但这是我的错，因为我没有把问题描述得更精确，我会看看是否可以编辑。我更感兴趣的是使用foldr生成函数的方法。你说的第一种实现方式基本上就是我尝试过的。 - user168064

@user168064 好的。在花费了约3个小时学习这个主题后，我也可以回答你想问的问题。我认为这应该是一个独立的第二个答案，而不是对此答案的编辑，所以另一个答案即将到来。 - Carl

Answer 3

这里是一个简单的删除程序，使用foldr实现：

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

- Dominik Auer

---

这并不是删除操作。删除只会移除第一个出现的元素。这就是所谓的“挑战”所在。 - user168064