8

简介： 这是来自 Miranda 考试的过去试题，但语法与 Haskell 非常相似。

问题： 以下表达式的类型是什么，它的作用是什么？（函数长度和交换的定义如下）。

(foldr (+) 0) . (foldr ((:) . length . (swap (:) [] )) [])

length [] = 0

length (x:xs) = 1 + length xs

swap f x y = f y x

笔记：

请随时用 haskell 语法回复 - 很抱歉将星星用作多型，但我不想将其错误地翻译成 haskell。基本上，如果一个变量具有 * 类型，而另一个具有 * 则意味着它们可以是任何类型，但它们必须都是相同的类型。如果一个有**，则意味着它可以但不需要与*具有相同的类型。我认为它对应于haskell 用法中的a、b、c 等。

我的工作至今

从长度的定义你可以看到它找到了任何东西列表的长度，所以这给出了

length :: [*] -> num.

从定义来看，我认为 swap 接受一个函数和两个参数，并产生交换了两个参数的函数，所以这给出了

swap :: (* -> ** -> ***) -> ** -> [*] -> ***

foldr 接受一个二进制函数（如加号）一个起始值和列表，并使用该函数从右到左折叠列表。这给

foldr :: (* -> ** -> **) -> ** -> [*] -> **)

我知道在函数组合中它是右关联的，因此例如第一个点 (.) 右侧的所有内容都需要生成一个列表，因为它将作为第一个 foldr 的参数给出。

foldr 函数输出单个值（折叠列表的结果），所以我知道返回类型将是某种多型而不是多型列表。

我的问题

我真的不确定从这里去哪里。我可以看到 swap 需要接受另一个参数，那么这个部分应用是否暗示整个事物是一个函数？我很困惑！

4

2 回答 2

9

你已经有了答案，我就一步步写下推导，方便一下子看出来：

xxf xs = foldr (+) 0 . foldr ((:) . length . flip (:) []) [] $ xs
       = sum         $ foldr ((:) . length . (: []))      []   xs
       = sum         $ foldr (\x -> (:) (length [x]))     []   xs
       = sum         $ foldr (\x r ->    length [x]:r)    []   xs
       = sum         $ map   (\x   ->    length [x]  )         xs
       = sum                            [length [x]  |    x <- xs]  
       = sum                            [ 1          |    x <- xs]
--     = length xs
xxf :: (Num n) => [a] -> n

所以，在米兰达，xxf xs = #xs. 我猜它的类型是:: [*] -> num米兰达语法。

Haskell's lengthis :: [a] -> Int，但正如这里定义的那样，这是:: (Num n) => [a] -> n因为它使用Num's(+)和两个文字，0and 1。

如果您在可视化时遇到问题foldr，那很简单

foldr (+) 0 (a:(b:(c:(d:(e:(...:(z:[])...))))))
      =      a+(b+(c+(d+(e+(...+(z+ 0)...)))))
      = sum [a, b, c, d, e, ..., z]
于 2012-04-29T17:57:43.087 回答
8

让我们一步一步来。

该length函数显然具有您描述的类型；在 Haskell 中是Num n => [a] -> n. 等效的 Haskell 函数是length（它使用Int而不是 any Num n）。

该swap函数接受一个函数来调用并反转它的前两个参数。你没有得到完全正确的签名；它是(a -> b -> c) -> b -> a -> c。等效的 Haskell 函数是flip.

该foldr函数具有您描述的类型；即(a -> b -> b) -> b -> [a] -> b. 等效的 Haskell 函数是foldr.

现在，让我们看看主表达式中的每个子表达式的含义。

表达式swap (:) []接受(:)函数并交换其参数。该(:)函数具有类型a -> [a] -> [a]，因此swapping 它会产生[a] -> a -> [a]；整个表达式因此具有类型a -> [a]，因为交换函数应用于[]. 结果函数的作用是它构造一个给定项目的列表。

为简单起见，让我们将该部分提取到一个函数中：

singleton :: a -> [a]
singleton = swap (:) []

现在，下一个表达式是(:) . length . singleton。该(:)函数仍然有类型a -> [a] -> [a]；函数的(.)作用是它组合函数，所以如果你有一个 functionfoo :: a -> ...和一个 function bar :: b -> a，foo . bar就会有 type b -> ...。因此，表达式(:) . length具有类型Num n => [a] -> [n] -> [n]（请记住length返回 a Num），并且表达式(:) . length . singleton具有类型Num => a -> [n] -> [n]。结果表达式的作用有点奇怪：给定任何类型的值a和一些列表，它将忽略a并将数字1添加到该列表中。

为简单起见，让我们从中创建一个函数：

constPrependOne :: Num n => a -> [n] -> [n]
constPrependOne = (:) . length . singleton

您应该已经熟悉foldr. 它使用函数对列表执行右折叠。在这种情况下，它会调用constPrependOne每个元素，因此表达式foldr constPrependOne []只是构造一个与输入列表长度相等的元素列表。所以让我们用它来做一个函数：

listOfOnesWithSameLength :: Num n => [a] -> [n]
listOfOnesWithSameLength = foldr constPrependOne []

如果你有一个清单[2, 4, 7, 2, 5]，你会[1, 1, 1, 1, 1]在申请时得到listOfOnesWithSameLength。

然后，该foldr (+) 0函数是另一个右折叠。相当于sumHaskell中的函数；它对列表的元素求和。

所以，让我们做一个函数：

sum :: Num n => [n] -> n
sum = foldr (+) 0

如果您现在编写函数：

func = sum . listOfOnesWithSameLength

...你得到结果表达式。给定一些列表，它会创建一个仅由 1 组成的等长列表，然后对该列表的元素求和。换句话说，它的行为与 完全一样length，只是使用了慢得多的算法。所以，最终的功能是：

inefficientLength :: Num n => [a] -> n
inefficientLength = sum . listOfOnesWithSameLength
于 2012-04-29T17:06:41.137 回答