Haskell / 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 :: (* -> ** -> ***) -> ** -> [*] -> ***foldr使用一个二进制函数(如加号)作为起始值，并使用该函数将列表从右到左折叠。这给了我们
foldr :: (* -> ** -> **) -> ** -> [*] -> **)我知道在函数组合中，它是正确的结合，因此，例如，第一个点(.)右边的所有内容都是正确的。需要生成一个列表，因为它将作为第一个文件夹的参数。
foldr函数输出一个值(折叠列表的结果)，因此我知道返回类型将是某种类型，而不是polytype列表。
我的问题
我真的不知道该去哪儿。我可以看到交换需要接受另一个论点，那么这个部分应用程序是否意味着整个事情是一个函数？我很困惑！
回答 2
Stack Overflow用户
发布于 2012-04-29 17:57:43
您已经得到了答案，我将一步一步地写下推导，这样就很容易一下子看到所有的内容：
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]Stack Overflow用户
发布于 2012-04-29 17:06:41
让我们一步一步地完成这件事。
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]类型，因此swapping它生成[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 []如果您有一个list [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 . listOfOnesWithSameLengthhttps://stackoverflow.com/questions/10373754
复制相似问题
腾讯云开发者
