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 usuage中的a，b，c等。

我至今

从长度的定义工作，你可以看到它发现的任何一个列表的长度，这给

length :: [*] -> num. 

从定义我想交换发生在一个函数和两个参数并产生交换两个参数的函数，所以这给出了

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

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

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

我知道在函数组合是右结合的如此例如一切到第一点（。）的权利需要产生一个列表，因为它会被作为参数给出的第一foldr相似。

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

我的问题

我不确定从这里到真的去。我可以看到交换需要接受另一个论证，这个部分应用意味着整个事情是一个函数吗？我很困惑！

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

Answer 2

让我们一步一步完成。

length功能显然有你描述的类型;在Haskell它是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返回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]，你会申请listOfOnesWithSameLength时得到[1, 1, 1, 1, 1]。

然后，foldr (+) 0函数是另一个正确的折叠。它相当于Haskell中的sum函数;它总结列表的元素。

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

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

如果你现在撰写功能：

func = sum . listOfOnesWithSameLength 

...你的结果表达式。给定一个列表，它会创建一个只包含相等长度的列表，然后对该列表的元素进行求和。换句话说，它的行为与length完全相同，只是使用更慢的算法。所以，最终的功能是：

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