Haskell中两个函数的最常见类型的"产品"

Question

我必须从Haskell中的给定函数中找到最通用的类​​型,或者更确切地说找到两个函数的"产品"的最一般类型(如果存在).我不确定但也许我应该使用Robinson统一算法,但我无法理解它.我需要一步一步的详细解决方案,所以我能理解.

功能 :

map :: (a ? b) ? [a] ? [b] 
iterate :: (a ? a) ? a ? [a]

如何找到最常用的类型

1. map iterate
2. iterate map

这不是作业.

Answer 1

我们问GHCi:

ghci> :type map . iterate
map . iterate :: (a -> a) -> [a] -> [[a]]
ghci> :type iterate . map
iterate . map :: (a -> a) -> [a] -> [[a]]

让我们看看它是如何得到它们的:

特定

map     :: (x -> y) -> [x] -> [y]
iterate :: (b -> b) -> b -> [b]
(.)     :: (s -> t) -> (r -> s) -> (r -> t)

并使用a ~ b表示"类型a和b相等".

然后map . iterate我们有

map :: s -> t where
 s ~ x -> y
 t ~ [x] -> [y]

iterate :: r -> s where
 r ~ b -> b
 s ~ b -> [b]

so
 x -> y ~ s ~ b -> [b]
=>
 x ~ b
 y ~ [b]
 t ~ [b] -> [[b]]

所以map . iterate :: (b -> b) -> [b] -> [[b]].

然后iterate . map我们有

iterate :: r -> s where
 s ~ b -> b
 t ~ b -> [b]

map :: s -> t where
 r ~ x -> y
 s ~ [x] -> [y]

so
 b -> b ~ s ~ [x] -> [y]
 b ~ [x]
 b ~ [y]
 x ~ y
 r ~ x -> x
 t ~ [x] -> [[x]]

所以iterate . map :: (x -> x) -> [x] -> [[x]].

虽然这些函数具有相同的类型,但它们的行为却截然不同.

• iterate . map将给定一个函数和一个长度列表k,产生一个无限长度列表列表k.
• map . iterate将给定一个函数和一个长度列表k,生成一个k无限列表长度列表.