haskell /米兰达 : Find the type of the function

Question

简介:这是来自 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 需要接受另一个参数，那么这个部分应用是否暗示整个事物是一个函数？我很困惑!

Answer 1

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

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 的 length是 :: [a] -> Int , 但正如这里定义的那样，它是 :: (Num n) => [a] -> n因为它使用 Num的 (+)和两个文字， 0和 1 .

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

foldr (+) 0 (a:(b:(c:(d:(e:(...:(z:[])...))))))
      =      a+(b+(c+(d+(e+(...+(z+ 0)...)))))
      = sum [a, b, c, d, e, ..., z]