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

Question

我这几天一直在研究褶皱.我可以实现简单的功能与他们一样length,concat和filter.什么我被困在试图与实现foldr类似功能delete,take和find.我用显式递归实现了这些,但对我来说,如何将这些类型的函数转换为右折叠似乎并不明显.

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

从阅读器中使用foldr实现插入haskell,如何使用foldr编写此函数？和使用foldr实现take,似乎我需要foldr用来生成一个函数然后做一些事情.但我并不真正理解这些解决方案,也不知道如何以delete这种方式实现.

您能否向我解释一下实现foldr懒惰版本功能的一般策略,比如我提到的那些功能.也许你也可以delete作为一个例子来实现,因为这可能是最简单的一个.

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

谢谢.

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

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,表示已找到它. 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.(我说"建议",因为有一些边缘情况,($!)即使WHNF也不会强制评估.)

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)) ([], [])

这不是获得结果的唯一方法.使用松懈结合或fst与snd作为元组访问器也将做的工作.但它是最小差异的变化.

这里最重要的一点是要非常小心处理传递给reduce函数的第二个参数foldr.您希望尽可能推迟检查第二个参数,以便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.