使用哈斯克尔的折叠器

Question

我正在学习Haskell，我一直在努力解决这个问题：

使用foldr编写func :: (a -> Bool) -> [a] -> [a](获取列表的元素，直到谓词为 false(

这是我到目前为止所拥有的：

func :: (a -> Bool) -> [a] -> [a]
func f li = foldr f True li

并得到以下错误：

Couldn't match expected type ‘[a]’ with actual type ‘Bool’

和

Couldn't match type ‘Bool’ with ‘Bool -> Bool’
Expected type: a -> Bool -> Bool
Actual type: a -> Bool

我有点困惑，因为我通过传递一个带有两个参数的函数并获取一个值来学习折叠器。例如，我通过调用

foldr (x -> y -> x*y*5) 1 [1,2,3,4,5] 

获取单个值，但不确定在将单个参数函数传递到 foldr 并返回列表时它是如何工作的。谢谢。

Answer 1

让我们先做一个更简单的情况，并编写一个使用 foldr 不执行任何操作的函数(分解列表并制作相同的列表(。我们来看看foldr的类型签名：

foldr :: (a -> b -> b) -> b -> [a] -> [b]

我们想写一个形式的表达式

foldr ?1 ?2 :: [a] -> [a]

现在这告诉我们(在foldr的签名中(我们可以用[a]替换b。

?2，我们还没有解决的一件事是我们替换列表末尾的内容，它的类型为b = [a].我们真的没有任何类型的a所以让我们尝试最愚蠢的事情：

foldr ?1 []

现在缺少的下一件事：我们有?1 :: a -> [a] -> [a].让我们为此编写一个函数。现在，我们可以用一个事情列表做两件合理的事情，另一件事，没有别的：

1. 将其添加到"开始">
2. 将其添加到末尾

我认为 1 更合理，所以让我们尝试一下：

myFunc = foldr (x xs -> x : xs) []

现在我们可以尝试一下：

> myFunc [1,2,3,4]
[1,2,3,4]

---

那么foldr这里的直觉是什么呢？好吧，一种思考方式是传递的函数被放入您的列表中而不是:，另一个项目替换[]所以我们得到

foldr f x [1,2,3,4]
——>
foldr f x (1:(2:(3:(4:[]))))
——>
f 1 (f 2 (f 3 (f 4 x)))

那么我们如何通过仔细选择我们的功能来做我们想做的事(本质上是用foldr实现takeWhile(呢？那么有两种情况：

1. 谓词在正在考虑的项目上为 true
2. 对于正在考虑的项目，谓词为 false，该谓词为 false

在情况 1 中，我们需要将我们的项目包含在列表中，这样我们就可以尝试像上面对恒等函数所做的那样做一些事情。

在情况 2 中，我们希望不包含该项目，并且不包含它之后的任何内容，因此我们可以返回[].

假设我们的函数对谓词"小于 3"做了正确的事情，以下是我们如何计算它：

f 1 (f 2 (f 3 (f 4 x)))
--T    T    F    F   (Result of predicate)
-- what f should become:
1 : (2 : ([]         ))
——>
[1,2]

所以我们需要做的就是实施f.假设谓词称为p。然后：

f x xs = if p x then x : xs else []

现在我们可以写

func p = foldr f [] where
f x xs = if p x then x : xs else []