3

我正在通过以下方式进行列表连接(例如,使用 GHC):

myConcat :: [[a]] -> [a]
myConcat xs = foldr (++) [] xs
myConcat    = foldr (++) []

有人可以向我解释一下上述定义为什么以及如何工作,而这个没有:

myConcat xs = foldr (++) []

是故意不允许最后一行代码(由于结构可能会变得混乱,它无用等原因)还是更深层次的东西,可能与currying有关......

我希望我能对此有所了解,这真的让我很困惑:/

后期编辑:除了下面给出的解释之外,我发现关于此事的一个很好的信息来源是第 1 章的“部分函数应用和柯里化”部分4 来自“Real World Haskell”一书的“函数式编程” 。该书可在线免费获取。

4

3 回答 3

7

让我们回顾一下不同的版本:

myConcat xs = foldr (++) [] xs

这是通常的方式,提供一个参数,由foldr. 类型是[[a]] -> [a],因为我们[[a]]在左侧有一个类型的参数,[a]当输入到右侧时会产生。

myConcat = foldr (++) []

这里foldr是部分应用的,所以我们返回一个函数,它可以接受一个额外的参数,一个列表列表。所以我们从右边得到的已经是我们需要的了,它不是“句法糖”,而是和第一个版本一样的另一种表达方式。类型又是[[a]] -> [a]:我们在左侧什么都没有,但在右侧返回该签名的函数。

myConcat xs = foldr (++) []

这里foldr也是部分应用的,我们返回一个可以像以前一样接受参数的函数,但是我们的定义有一个额外的参数xs,它没有在右侧使用。编译器不“知道”我们想要将这个参数应用于右侧。类型是t -> [[a]] -> [a]。为什么?

假设你有一个平方函数:

sqr :: Int -> Int 
sqr x = x*x

您所做的基本上与提供一个未使用的附加参数相同:

sqr:: Int -> t -> Int 
sqr x y = x*x

该函数仍然“有效”,例如sqr 3 "bla"产生 9,但类型签名已关闭,未使用的参数是……呃,未使用。未使用的参数没有固定类型,因为它实际上可以是“任何东西”,没关系。所以它t在签名中获取类型变量 ()。

于 2011-07-22T06:34:39.850 回答
3

好吧,让我们看一下curried 函数 foldr的类型签名:

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

所以foldr接受一个二进制函数(即a->b->b)、一个b值、一个值列表a,并返回一个b值。

让我们也看看文档foldr获得更清晰的定义:

foldr,应用于二元运算符、起始值(通常是运算符的右标识)和列表,使用二元运算符从右到左减少列表:

现在,让我们看一下类型签名myConcat xs = foldr (++) []

> :t myConcat
myConcat :: t -> [[a]] -> [a]

嗯……这不是我们想要的……

问题是您从未提供foldrtype 的值[a]。所以现在,myConcat需要一些任何类型的值来满足xs 类型的值[a]来完成foldr (++) [],比如:

> myConcat 2 [[1,2],[3,4]] 
[1,2,3,4]
> myConcat Nothing [[1,2],[3,4]] 
[1,2,3,4]

这行得通,但第一个论点只是浪费。

但是,如果我们将该xs值传递给foldr (++) [],例如:

myConcat xs = foldr (++) [] xs

并检查其类型签名

> :t myConcat
myConcat :: [[a]] -> [a]

啊,好多了。现在 myConcat 使用xs来完成该foldr功能。

此外,myConcat = foldr (++) []也有效,实际上是无点式编程的一个示例。如果我们检查 的类型签名foldr (++) []

> :t foldr (++) []
foldr (++) [] :: [[a]] -> [a]

由于我们已经通过部分应用foldr提供了它的前两个参数,我们得到了一个函数,它将接受一个值并执行我们想要的操作!所以我们只是将它分配给一个名字,它就像上面的例子一样工作,但我们不需要显式传递参数![[a]]

> let myConcat = foldr (++) []
> :t myConcat
myConcat :: [[a]] -> [a]
> myConcat [[1,2],[3,4]]
[1,2,3,4]
于 2011-07-22T06:35:37.253 回答
2
myConcat xs = foldr (++) []

具有t -> [[a]] -> [a]与其他两个不同的类型[[a]] -> [a]

于 2011-07-22T06:14:46.180 回答