使用Haskell‘Haskell

Question

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

使用func :: (a -> Bool) -> [a] -> [a]编写foldr (取列表中的元素，直到谓词为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。例如，我通过调用

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)))

那么，我们如何通过谨慎地选择我们的函数来实现我们想要的(本质上是用takeWhile实现foldr)呢？嗯，有两种情况：

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

在第一种情况下，我们需要将我们的项目包括在列表中，这样我们就可以尝试像上面使用身份函数那样做一些事情。

在第二种情况下，我们不想包含项目，也不想在它之后包含任何内容，所以我们只需要返回[]。

假设我们的函数对谓词“小于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 []