如何在Haskell中使用foldr实现删除 [英] How to implement delete with foldr in Haskell
问题描述
length ， concat 和 filter 。我坚持的是试图用 foldr 来实现，比如 delete ， take 和查找。我已经实现了这些显式递归，但它似乎并不明显如何将这些类型的函数转换为正确的折叠。
我已经研究了Graham Hutton的教程和伯尼教皇。模仿Hutton的 dropWhile ，我可以用 foldr delete >但它在无限列表上失败。
阅读在haskell中使用foldr实现插入，如何使用foldr编写此函数？和，似乎我需要使用 foldr 生成一个函数，然后做一些事情。但我并不十分理解这些解决方案，也不知道如何以这种方式实现 delete 。
你能否向我解释一个实现 foldr
懒惰版本的一般策略，就像我提到的那些。也许你还可以实现 delete 作为例子，因为这可能是最简单的一个。 我在寻找对于初学者可以理解的详细解释。我对解决方案不感兴趣，我想开发一种理解，以便我可以自己想出类似问题的解决方案。
谢谢。
编辑：在撰写的时候有一个有用的答案，但它不是我想要的。我更感兴趣的是使用foldr生成一个函数的方法，然后它执行一些操作。我的问题中的链接有这样的例子。我不太了解这些解决方案，所以我想了解更多关于此方法的信息。
删除是一种模态搜索。它有两种不同的操作模式 - 无论它是否已经找到结果。您可以使用 foldr 来构造一个函数，在每个元素被选中时将状态传递给行。因此，在 delete 的情况下，状态可以是简单的 Bool 。它不完全是最好的类型，但它可以。
一旦确定了状态类型，就可以开始处理 foldr code>施工。我将通过我的方式来解决问题。我将启用 ScopedTypeVariables ，以便我可以更好地注释子表达式的类型。你知道状态类型，你知道你需要 foldr 来生成一个取得该类型值的函数，并返回所需最终类型的值。
{ - ＃LANGUAGE ScopedTypeVariables＃ - }
delete ::全部公式a => a - > [a] - > [a]
删除一个xs = foldr f undefined xs undefined
其中
f :: a - > （Bool - > [a]） - > （Bool - > [a]）
f x g =未定义
这是一个开始。 g 的确切含义在这里有点棘手。它实际上是处理列表的其余部分的函数。事实上，把它看作是一个延续是准确的。它绝对代表了您执行折叠的其余部分，无论您选择传递什么状态。鉴于此，现在是时候弄清楚应该在哪些未定义地点放置什么。
{ - ＃LANGUAGE ScopedTypeVariables＃ - }
delete :: forall a。公式a => a - > [a] - > [a]
删除一个xs = foldr f undefined xs undefined
其中
f :: a - > （Bool - > [a]） - > （Bool - > [a]）
f x g found | x == a&& not found = g True
|否则= x：g找到
这似乎相对简单。如果当前元素是正在搜索的元素，但尚未找到，请不要输出它，并继续设置为 True 的状态，表示它是被发现。 否则，输出当前值并继续当前状态。这只会将其余的参数留给 foldr 。最后一个是初始状态。另一个是空列表的状态函数。
{ - ＃LANGUAGE ScopedTypeVariables＃ - }
删除:: forall a。公式a => a - > [a] - > [a]
删除一个xs = foldr f（const []）xs False
其中
f :: a - > （Bool - > [a]） - > （Bool - > [a]）
f x g found | x == a&& not found = g True
|否则= x：g找到
不管状态如何，当空列表产生一个空列表遇到。最初的状态是找到的元素尚未找到。
这种技术也适用于其他情况。例如， foldl 可以这样写成 foldr 。如果你看看 foldl 作为一个重复变换初始累加器的函数，那么你可以猜测这是正在生成的函数 - 如何变换初始值。
{ - ＃LANGUAGE ScopedTypeVariables＃ - }
foldl :: forall a b。 （a→b→a）→> a - > [b] - > a
foldl f z xs = foldr g id xs z
其中
g :: b - > （a - > a） - > （a - > a）
gx cont acc = undefined
基本情况不是当问题被定义为操纵初始累加器，在那里命名为 z 时，太棘手。空列表是身份转换， id ，传递给创建函数的值是 z 。
执行 g 会更棘手。它不能只是盲目地在类型上完成，因为有两种不同的实现使用所有期望的值和类型检查。这是一种类型不够的情况，您需要考虑可用功能的含义。
让我们从看起来像他们的值的清单开始应该使用，以及它们的类型。看起来像他们必须在 g 主体中使用的东西是 f :: a - > b - > a ， x :: b ， cont ::（a - > a） ，和 acc :: a 。 f 明显地将 x 作为它的第二个参数，但是有一个问题需要使用续。为了找出它的位置，记住它表示处理列表的其余部分返回的转换函数，并且 foldl 处理当前元素，然后传递该结果处理到列表的其余部分。
{ - ＃LANGUAGE ScopedTypeVariables＃ - }
foldl： ：forall a b。 （a→b→a）→> a - > [b] - > a
foldl f z xs = foldr g id xs z
其中
g :: b - > （a - > a） - > （a - > a）
gx 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
其中
g :: b - > （a - > a） - > （a - > a）
g x cont acc = cont $！ f acc x
区别在于（$！）用于在传递给 cont 之前对 f acc x 进行评估。 （我说建议是因为有一些边缘情况下，即使到WHNF，（$！）也不会强制进行评估。）
I've been studying folds for the past few days. I can implement simple functions with them, like length, concat and filter. What I'm stuck at is trying to implement with foldr functions like delete, take and find. I have implemented these with explicit recursion but it doesn't seem obvious to me how to convert these types of functions to right folds.
I have studied the tutorials by Graham Hutton and Bernie Pope. Imitating Hutton's dropWhile, I was able to implement delete with foldr but it fails on infinite lists.
From reading Implement insert in haskell with foldr, How can this function be written using foldr? and Implementing take using foldr, it would seem that I need to use foldr to generate a function which then does something. But I don't really understand these solutions and don't have an idea how to implement for example delete this way.
Could you explain to me a general strategy for implementing with foldr lazy versions of functions like the ones I mentioned. Maybe you could also implement delete as an example since this probably is one of the easiest.
I'm looking for a detailed explanation that a beginner can understand. I'm not interested in just solutions, I want to develop an understanding so I can come up with solutions to similar problems myself.
Thanks.
Edit: At the moment of writing there is one useful answer but it's not quite what I was looking for. I'm more interested in an approach that uses foldr to generate a function, which then does something. The links in my question have examples of this. I don't quite understand those solutions so I would like to have more information on this approach.
delete is a modal search. It has two different modes of operation - whether it's already found the result or not. You can use foldr to construct a function that passes the state down the line as each element is checked. So in the case of delete, the state can be a simple Bool. It's not exactly the best type, but it will do.
Once you have identified the state type, you can start working on the foldr construction. I'm going to walk through figuring it out the way I did. I'll be enabling ScopedTypeVariables just so I can annotate the type of subexpressions better. One you know the state type, you know you want foldr to generate a function taking a value of that type, and returning a value of the desired final type. That's enough to start sketching things.
{-# 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
It's a start. The exact meaning of g is a little bit tricky here. It's actually the function for processing the rest of the list. It's accurate to look at it as a continuation, in fact. It absolutely represents performing the rest of the folding, with your whatever state you choose to pass along. Given that, it's time to figure out what to put in some of those undefined places.
{-# 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
That seems relatively straightforward. If the current element is the one being searched for, and it hasn't yet been found, don't output it, and continue with the state set to True, indicating it's been found. otherwise, output the current value and continue with the current state. This just leaves the rest of the arguments to foldr. The last one is the initial state. The other one is the state function for an empty list. Ok, those aren't too bad either.
{-# 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
No matter what the state is, produce an empty list when an empty list is encountered. And the initial state is that the element being searched for has not yet been found.
This technique is also applicable in other cases. For instance, foldl can be written as a foldr this way. If you look at foldl as a function that repeatedly transforms an initial accumulator, you can guess that's the function being produced - how to transform the initial value.
{-# 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
The base cases aren't too tricky to find when the problem is defined as manipulating the initial accumulator, named z there. The empty list is the identity transformation, id, and the value passed to the created function is z.
The implementation of g is trickier. It can't just be done blindly on types, because there are two different implementations that use all the expected values and type-check. This is a case where types aren't enough, and you need to consider the meanings of the functions available.
Let's start with an inventory of the values that seem like they should be used, and their types. The things that seem like they must need to be used in the body of g are f :: a -> b -> a, x :: b, cont :: (a -> a), and acc :: a. f will obviously take x as its second argument, but there's a question of the appropriate place to use cont. To figure out where it goes, remember that it represents the transformation function returned by processing the rest of the list, and that foldl processes the current element and then passes the result of that processing to the rest of the list.
{-# 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
This also suggests that foldl' can be written this way with only one tiny change:
{-# 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
The difference is that ($!) is used to suggest evaluation of f acc x before it's passed to cont. (I say "suggest" because there are some edge cases where ($!) doesn't force evaluation even as far as WHNF.)
这篇关于如何在Haskell中使用foldr实现删除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
