Haskell中两个函数中最通用的"product"类型
The most general type of "product" of two functions in Haskell
我必须从 Haskell 中的给定函数中找到最一般的类型,或者更确切地说,找到两个函数的 "product" 中最一般的类型(如果存在)。我不确定,但也许我应该使用 Robinson 统一算法,但我无法理解。我需要一个详细的解决方案,一步一步,这样我就明白了。
函数:
map :: (a → b) → [a] → [b]
iterate :: (a → a) → a → [a]
如何为
找到最通用的类型
map iterate
iterate map
这不是作业。
让我们问问 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
表示 "types a
and b
are equal"。
然后在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
的无限列表列表。
首先,明确写出所有省略的括号。
要导出a -> b
类型的函数和c
类型的值的应用类型,我们需要统一a
和c
类型,注意任何结果类型等价。然后应用程序的类型是 b
,在上述等价项下。规则是:
f :: a → b
x :: c
----------
f x :: b , { a ~ c }
要半机械地找到这个,只需对齐类型并注意等价:
map :: ( a1 → b1 ) → ([a1] → [b1])
iterate :: (a2 → a2) → (a2 → [a2])
--------------------------
{ a1 ~ (a2 → a2) , b1 ~ (a2 → [a2]) }
所以,
map iterate :: [a1] → [b1]
从等价代入,我们得到
:: [a2 → a2] -> [a2 → [a2]]
现在我们可以将 a2
重命名回 a
,或 t
,或其他名称。你的第二个例子是类似的:
iterate :: ( a2 → a2 ) → (a2 → [a2])
map :: (a1 → b1) → ([a1] → [b1])
---------------------------
{ a2 ~ a1 → b1 , a2 ~ [a1] → [b1] }
由于 a2 ~ a2
,我们得到 a1 → b1 ~ [a1] → [b1]
:
a1 → b1
[a1] → [b1]
--------------
{ a1 ~ [a1] , b1 ~ [b1] }
两种等价都是不可能的,定义一个无限类型。所以第二个例子在 Haskell:
中没有类型
*Main> :t map iterate
map iterate :: [a -> a] -> [a -> [a]]
*Main> :t iterate map
:1:9:
Occurs check: cannot construct the infinite type: a ~ [a]
Expected type: (a -> b) -> a -> b
Actual type: (a -> b) -> [a] -> [b]
In the first argument of 'iterate', namely 'map'
In the expression: iterate map
:1:9:
Occurs check: cannot construct the infinite type: b ~ [b]
Expected type: (a -> b) -> a -> b
Actual type: (a -> b) -> [a] -> [b]
In the first argument of 'iterate', namely 'map'
In the expression: iterate map
我必须从 Haskell 中的给定函数中找到最一般的类型,或者更确切地说,找到两个函数的 "product" 中最一般的类型(如果存在)。我不确定,但也许我应该使用 Robinson 统一算法,但我无法理解。我需要一个详细的解决方案,一步一步,这样我就明白了。
函数:
map :: (a → b) → [a] → [b]
iterate :: (a → a) → a → [a]
如何为
找到最通用的类型map iterate
iterate map
这不是作业。
让我们问问 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
表示 "types a
and b
are equal"。
然后在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
的无限列表列表。
首先,明确写出所有省略的括号。
要导出a -> b
类型的函数和c
类型的值的应用类型,我们需要统一a
和c
类型,注意任何结果类型等价。然后应用程序的类型是 b
,在上述等价项下。规则是:
f :: a → b
x :: c
----------
f x :: b , { a ~ c }
要半机械地找到这个,只需对齐类型并注意等价:
map :: ( a1 → b1 ) → ([a1] → [b1])
iterate :: (a2 → a2) → (a2 → [a2])
--------------------------
{ a1 ~ (a2 → a2) , b1 ~ (a2 → [a2]) }
所以,
map iterate :: [a1] → [b1]
从等价代入,我们得到
:: [a2 → a2] -> [a2 → [a2]]
现在我们可以将 a2
重命名回 a
,或 t
,或其他名称。你的第二个例子是类似的:
iterate :: ( a2 → a2 ) → (a2 → [a2])
map :: (a1 → b1) → ([a1] → [b1])
---------------------------
{ a2 ~ a1 → b1 , a2 ~ [a1] → [b1] }
由于 a2 ~ a2
,我们得到 a1 → b1 ~ [a1] → [b1]
:
a1 → b1
[a1] → [b1]
--------------
{ a1 ~ [a1] , b1 ~ [b1] }
两种等价都是不可能的,定义一个无限类型。所以第二个例子在 Haskell:
中没有类型*Main> :t map iterate
map iterate :: [a -> a] -> [a -> [a]]
*Main> :t iterate map
:1:9:
Occurs check: cannot construct the infinite type: a ~ [a]
Expected type: (a -> b) -> a -> b
Actual type: (a -> b) -> [a] -> [b]
In the first argument of 'iterate', namely 'map'
In the expression: iterate map
:1:9:
Occurs check: cannot construct the infinite type: b ~ [b]
Expected type: (a -> b) -> a -> b
Actual type: (a -> b) -> [a] -> [b]
In the first argument of 'iterate', namely 'map'
In the expression: iterate map