Haskell 使用 foldr

Question

嗨，我是 Haskell 的新手，我有点迷茫。我被要求这样做，但无法解决。

仅使用 foldr ， bool 运算(||)和 False , 定义一个函数

or_list :: [Bool] -> Bool

以便

or_list [b1, b2,...,bn] = b1 || b2 ||...|| bn

注意

or_list [] = False

我想出了这样的事情

or_list :: [Bool] -> Bool
or_list [0..n] = foldr False (||) [0..n] 

但真的不明白如何 foldr作品。如果有人能指出我正确的道路，那将是一个很大的帮助。

Answer 1

你的定义几乎是正确的，但你的语法有点不对。你不能有一个模式匹配

or_list [0..n] = ...

这只是无效的语法。事实上，你根本不需要模式匹配，你可以这样做

or_list bs = foldr False (||) bs

下一个问题可以通过查看 foldr 来揭示的类型:

foldr :: (Bool -> Bool -> Bool) -> Bool -> [Bool] -> Bool
-- Simplified from its more general type

请注意，它的第一个参数是一个接受两个 bool 值的函数，第二个参数只是一个 bool 值。你有

foldr False (||) bs

但是 False不是函数和 (||)不是 bool 值。如果你交换它们，你会得到

foldr (||) False bs

然后你的定义是正确的!

这是如何运作的？折叠是简单递归的概括，通常您有一个函数，您将其应用于一个参数，该参数也取决于最后计算的值。这些类型的递归对于将值列表转换为单个值很有用。 foldr的定义非常简单，我认为这有助于解释折叠的工作原理

foldr f initial [] = initial
foldr f initial (x:xs) = f x (foldr f initial xs)

所以如果我们要插入一些值并扩展它

  foldr (||) False [False, False, True]
= False || (foldr (||) False [False, True])
= False || (False || (foldr (||) False [True]))
= False || (False || (True || (foldr (||) False [])))
= False || (False || (True || (False)))
= False || (False || True)
= False || True
= True

另一种看待它的方式是它取代了 :来自 f和 []来自 initial在一个列表中，所以如果你有

False : False : True : []

你申请 foldr (||) False到它，你会替换每个 :来自 ||和 []与 False ，关联权限( r 的 foldr 部分)，所以

False || (False || (True || (False)))

这与我们上面得到的扩展相同。 A foldl在相反的协会工作，所以 foldl (||) False好像

(((False) || False) || False) || True
-- ^ initial

所以区别基本上是初始值卡在哪一端以及括号在哪里。