8

在完成99 题练习中的第一个问题（“查找列表的最后一个元素”）后，我想看看我的解决方案与其他解决方案相比如何，我找到了这个解决方案。

myLast' = foldr1 (const id)

该文档似乎表明foldr1需要两个参数，第一个是函数，第二个是列表。但是这个定义似乎只将函数作为参数。是否有像这样传递的参数的隐式定义？

myLast' xs = foldr1 (const id) xs

我查找了、 和的定义foldr1，但我很难理解这三个如何协同工作以返回列表中的最后一项。constid

4

4 回答 4

6

你完全正确。在 Haskell 中，一个接受两个参数的函数实际上可以被视为一个接受一个参数并返回另一个接受一个参数的函数的函数；这被称为柯里化。请注意，函数签名为foldr1：

(a -> a -> a) -> [a] -> a

虽然我们通常认为它是“一个以函数和列表为参数并返回值的函数”，但它实际上是“一个以函数为参数并返回一个以列表为参数并返回值的函数” .

于 2013-09-03T17:30:36.230 回答
3

正如 mipadi 解释的那样，该函数正在被柯里化。这解释了 list 参数是如何到达那里的，但可能没有解释实际 fold 是如何工作的。

这const id有点棘手。foldr1期望得到具有类型的东西a -> a -> a。这些函数的定义是

const :: x -> y -> x
const x y = x

id :: x -> x
id x = x

因此，将所有这些组合在一起，我们有

const id =
\ y -> id =
\ y -> \ x -> x =
\ y x -> x

换句话说，与;const id做同样的事情 flip const它是一个 2 参数函数，它丢弃第一个参数，并返回第二个参数。事实并非如此。恕我直言，flip const会更清楚。

foldr1将使用旧值作为第一个参数调用此函数，并将下一个列表元素作为第二个参数。此函数始终返回下一个列表元素。最终输出foldr是函数的最后一个输出，它将是整个列表的最后一个元素。

于 2013-09-03T18:24:10.300 回答
0

是的，您对不需要所有参数的函数的直觉是正确的。当一个函数将另一个函数作为参数返回另一个函数作为结果时，它被称为“currying”。请参阅：http ://en.wikipedia.org/wiki/Currying 。

（作为旁注，这实际上是由Haskell Curry发现（或重新发现）的，这就是我们的 Haskell 得名的原因。）

如果柯里化的想法仍然需要时间来理解，这可能会有所帮助：实际上在Prelude被调用的curry和中定义了两个函数uncurry。它们具有以下类型：

Prelude> :t curry
curry :: ((a, b) -> c) -> a -> b -> c
Prelude> :t uncurry
uncurry :: (a -> b -> c) -> (a, b) -> c

uncurry接受一个 2 参数的curried函数（或一个接受一个参数的函数并返回一个参数的函数的函数）并生成一个uncurrried函数，或者一个同时接受所有参数的函数（作为一个元组）。

curry，正如您可能通过名称和类型所暗示的那样，采用另一种方式，因此它接受一个柯里化函数（一个同时接受所有参数的函数）并生成一个接受一个参数并返回一个函数的函数另一个论点。

大多数编程语言默认以非柯里化方式工作，您提供所有参数并获得结果，而 Haskell 默认情况下是柯里化的。

现在以 为例uncurry，我们可以采用一个简单的函数，(+)：

Prelude> :t (+)
(+) :: Num a => a -> a -> a
Prelude> (+) 1 2
3
Prelude> :t (+)
(+) :: Num a => a -> a -> a
Prelude> :t uncurry (+)
uncurry (+) :: Num c => (c, c) -> c
Prelude> uncurry (+) (1,2)
3

const而且，如果我们愿意，我们也可以这样做：

Prelude> :t const
const :: a -> b -> a
Prelude> const 1 2
1
Prelude> :t uncurry const
uncurry const :: (c, b) -> c
Prelude> uncurry const (1,2)
1

但是有一个非柯里化的版本const并不是很有用，因为如果你必须预先指定所有参数，那么让一个函数接受两个参数并总是返回第一个参数是没有意义的。

const之所以有用，正是因为它是柯里化的，并且可以在需要一个函数的地方给出，该函数接受两个参数并简单地返回第一个参数。

比如在 中foldr1：

Prelude> :t foldr1
foldr1 :: (a -> a -> a) -> [a] -> a

其中第一个参数是两个参数的柯里化函数。并且由于函数的返回值可以是一个函数，它也可以是这样的const：

Prelude> :t const id
const id :: b -> a -> a

const id只需接受任何类型的参数b并返回id函数。

所以如果我们可以const id一步一步申请：

Prelude> :t const id 1
const id 1 :: a -> a

const id 1或者const id anyOtherValueHere只返回 id 函数。可以这样使用：

Prelude> :t const id "Giraffe" 100
const id "Giraffe" 100 :: Num a => a
Prelude> const id "Giraffe" 100
100
Prelude> :t const id (\a b -> undefined) 100
const id (\a b -> undefined) 100 :: Num a => a
Prelude> const id (\a b -> undefined) 100
100

所以，const真的忽略了它的第二个论点。直接在上面，就像申请id100一样。

因此，foldr1 (const id)只需获取一个列表并继续应用于id每组两个元素并保留第二个（因为const id返回id传入的第二个参数的值），直到我们拥有最后一个元素。

于 2013-09-03T18:44:54.820 回答
0

您是正确的，您的两个示例可以相互替换。这可以被认为是代数抵消，就像在代数课中一样。

f x y = g x y

y我可以在每一边取消：

f x = g x

现在我可以取消两边的 x ：

f = g

查看foldr vs foldl 和 foldl'的wiki 页面，了解有关 foldr 的更多信息。

为了了解 myLast' 的工作原理，我们可以做一些代数替代。

myLast' [1, 2, 3]

== foldr1 (const id) [1, 2, 3]

现在我们应该使用 in-specific 的定义foldr1：foldr1 f (x:xs) = f x (foldr1 f xs)

== (const id) 1 (foldr1 (const id) [2, 3])

const id结果证明其类型 sig 与 sigb -> a -> a相同，flip const并且它的行为也相同，这是一个忽略其第一个参数并返回第二个参数的函数。示例：(const id) 1 3 == 3 * 更多信息请参见下文 *

== foldr1 (const id) [2, 3]

== foldr1 (const id) [3]

== 3

最后一步可能不是您所期望的，但如果您检查它的定义，foldr1它包含：

foldr1 _ [x] =  x

当它们只是列表中的一个元素并返回它时，哪个模式匹配。

*是如何const id工作的？

const返回它的第一个参数并忽略它，所以

const id 3   == id

const id 3 4 == id 4 == 4
于 2013-09-03T18:30:22.270 回答