5

我无法解释 foldl 的函数签名。我了解它是如何工作的，但我不确定它与签名有何关系。

我有几个关于它的细节的问题

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

foldr (+) 5 [1,2,3,4]

似乎第一个参数需要一个加法函数：

(a -> b -> b)

在函数参数中，到底发生了什么？在这种情况下，本节是否将最右边的整数a应用于累加器b以产生另一个整数 9？在此之后，它是否会返回一个以累加器为参数的函数？

在此之后，下面的最后两个参数是什么意思？

[a] -> b

非常感谢。

4

3 回答 3

5

当您传递(+)给您的第一个参数时，foldr隐式声明它a与b. 这会让人感到困惑，因为我们倾向于重用名称，但如果我使用相同的命名空间为类型变量编写它们

(+)       :: Num i => i -> i -> i
foldr     :: (a -> b -> b) -> b -> [a] -> b
foldr (+) :: Num i => i -> [i] -> i

其中第三行意味着那个i ~ a，i ~ b因此，通过传递性，a ~ b。此外，这里可能更清楚地看到，第一个剩余参数foldr (+)是折叠的“初始”值，而[i]位是我们正在压缩、折叠、减少的列表。

foldr (+) 0用它更常见的名称来称呼可能会更清楚， sum :: Num a => [a] -> a. 我们也有foldr (*) 1as product :: Num a => a -> [a]。

所以是的，您对累加器功能如何表现的描述foldr (+)是完全正确的，但比一般功能更具体。例如，我们可以使用foldr构建一个Map.

foldr (\(k, v) m -> Map.insert m k v) Map.empty :: Ord k => [(k, v)] -> Map k v

在这种情况下，累加器函数获取我们的关联列表并不断将值插入到我们的 accumulat*ing*Map中，它开始为空。为了在这里彻底彻底，让我再次将类型全部写出来

(\(k, v) -> m -> Map.insert m k v)       :: Ord k => (k, v) -> Map k v -> Map k v
foldr                                    :: (a -> b -> b) -> b -> [a] -> b
foldr (\(k, v) -> m -> Map.insert m k v) :: Ord k => Map k v -> [(k, v)] -> Map k v

我们在哪里强制a ~ (k, v)和b ~ Map k v。

作为对此事的最终看法，这里是 foldr 的定义，带有一些暗示性的变量名称

foldr _    b []     = b
foldr (<>) b (a:as) = a <> foldr f b as

所以你可以看到如何(<>) :: a -> b -> b组合a和b类型。我们可以显式地“运行”这个定义，看看它是如何构建计算的。

foldr (+) 0 [1,2,3]
1 + (foldr (+) 0 [2,3])
1 + (2 + (foldr (+) 0 [3]))
1 + (2 + (3 + (foldr (+) 0 [])))
1 + (2 + (3 + 0))
1 + (2 + 3)
1 + 5
6

当我们像上面的例子那样使用非对称操作时，这可能会更清楚Map。下面我用它{{ k -> v, k -> v }}来表示，Map因为它不能直接打印。

-- inserts a single (k,v) pair into a Map
ins :: Ord k => (k, v) -> Map k v -> Map k v
ins (k, v) m = Map.insert m k v

foldr ins Map.empty [('a', 1), ('b', 2)]
ins ('a', 1) (foldr ins Map.empty [('b', 2)])
ins ('a', 1) (ins ('b', 2) (foldr ins Map.empty []))
ins ('a', 1) (ins ('b', 2) Map.empty)
ins ('a', 1) (ins ('b', 2) {{  }})
ins ('a', 1) {{ 'b' -> 2 }}
{{ 'b' -> 2, 'a' -> 1 }}
于 2013-10-26T01:42:10.500 回答
1

这取决于你怎么看了。第一步产生(+) 1 (foldr (+) 5 [2,3,4])。当您尝试使用折叠的结果时，这将强制对 (+) 的第二个参数求值，并且由于 (+) 是严格的，这会解开整个列表。最后一步产生(+) 1 ((+) 2 ((+) 3 ((+) 4 5))). 所以，是的，添加的前两个数字是 4 和 5，但这不是 foldr 所做的第一件事，在这种情况下，您将首先将列表替换为 thunk 树，然后评估它以获得所有的总和数字和 5。

在函数不严格的情况下，用 thunk 替换列表是很好的 - 这样您可以只评估必要的数量，甚至可能是无限列表。在函数很严格的情况下，考虑用 重写是有意义的foldl'。

于 2013-10-26T09:38:09.783 回答
1

这是 foldr 的类型签名：

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

它采用一个函数（称为step），该函数采用下一个值（an a）和累加值（a b）并产生一个新的累加值（也是 a b）

step :: a -> b -> b

和一个初始累加器值（a b）：

initialValue :: b

以及要折叠的输入列表（a 的列表）：

inputs :: [a]

最后你得到一个输出 (a b )

output :: b

所以你得到一个一般的形式：

output = foldr step initialValue inputs
于 2013-10-26T12:54:36.083 回答