Haskell/Miranda:找到函数的类型

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 usuage中的a,b,c等.

我的工作到目前为止

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

length :: [*] -> num.

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

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

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.我猜它的类型是:: [*] -> numMiranda语法.

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]

Answer 2

让我们一步一步来看看.

该length功能显然具有您描述的类型; 在哈斯克尔这是Num n => [a] -> n.等效的Haskell函数是length(它使用Int而不是任何Num n).

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

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

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

表达式swap (:) []接受(:)函数并交换其参数.该(:)函数具有类型a -> [a] -> [a],所以swap平它产生[a] -> a -> [a]; 因此,整个表达式具有类型,a -> [a]因为应用了交换函数[].结果函数的作用是它构造给定该项的一个项的列表.

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

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

现在,下一个表达是(:) . length . singleton.该(:)功能还具有类型a -> [a] -> [a]; 该(.)函数的作用是它组成函数,所以如果你有一个函数foo :: a -> ...和一个函数bar :: b -> a,foo . bar就会有类型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功能是另一个右折.它等同sum于Haskell中的函数; 它总结了列表的元素.

那么,让我们做一个函数:

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

如果你现在组成函数:

func = sum . listOfOnesWithSameLength

...你得到了结果表达式.给定一些列表,它创建一个等长的列表,只包含一个列表,然后对该列表的元素求和.换句话说,它表现得非常像length,只使用更慢的算法.所以,最终的功能是:

inefficientLength :: Num n => [a] -> n
inefficientLength = sum . listOfOnesWithSameLength