哈斯克尔的类型推断奇怪 [英] Haskell's type inference strangeness
问题描述
Prelude> :t Data.Map.lookup
Data.Map.lookup :: Ord k => k - > Data.Map.Map k a - >也许一个
Prelude> :t flip Data.Map.lookup
flip Data.Map.lookup :: Ord a => Data.Map.Map a a1 - > a - >也许a1
Prelude>让look = flip Data.Map.lookup
加载package array-0.3.0.2 ...链接... done。
加载包装容器-0.4.0.0 ...链接...完成。
前奏> :t look
look :: Data.Map.Map()a - > () - >也许是
为什么看起来
的推断类型不同于的类型flip Data.Map.lookup
?
给你一些背景。最初我有一个小程序,并试图找出它为什么会产生编译器错误:
pre $ 将限定的Data.Map导入为M
类型A =字符串
类型B =字符串
数据C = C1 | C2 | C3
导出(Eq,Ord)
类型D =字符串
z :: A - > M.Map A B - > M.Map B C - > M.Map C D - >也许D
za aToB bToC cToD =查看aToB a>> =查看bToC>> = look cToD
其中look = flip M.lookup
Ghci的反应:
Prelude> :加载main.hs
[1之1]编译Main(main.hs,解释)
失败,模块加载:无。
main.hs:10:52:
实际类型为[[Char]'
的预期类型`C')预期类型:C - >也许D
实际类型:A - >也许a0
在`look'调用的返回类型中
在'(> =)'的第二个参数中,即`look cToD'
$ c $我发现这个变体编译得很好(类型定义是相同的):
$ b
$ b pre> x :: A - > M.Map A B - > M.Map B C - >也许C
x a aToB bToC =看aToB a>> = look bToC
where look = flip M.lookup
:: A - > M.Map A B - > M.Map B C - > M.Map C D - >也许D
ya aToB bToC cToD =(xa aToB bToC)>> = look cToD
where look = flip M.lookup
经过一些实验后发现,如果我明确地放置了类型的外观,那么第一个版本也可以很好地编译:
z :: A - > M.Map A B - > M.Map B C - > M.Map C D - >也许D
a aToB bToC cToD =看aToB a>> =看bToC>> = look cToD
where look ::(Ord a)=> M.Map a b - > a - >也许b
look = flip M.lookup
这引出我的第一个问题。 / p>
默认情况下,顶级绑定是非多态的,除非给出明确的类型说明符。这被称为'单态限制'。由于没有给出类型说明符,GHC必须选择一种方法来在定义函数时实例化 k
。它碰巧选择了 k =()
。
很多vtable调用在最终的编译代码中;通过强制这些在编译时解决,除非另有明确说明,可以避免这种开销。这个决定颇具争议。 GHC支持扩展来禁用通过传递 -XNoMonomorphismRestriction
。
来完全限制单态。
Look at this output from ghci:
Prelude> :t Data.Map.lookup
Data.Map.lookup :: Ord k => k -> Data.Map.Map k a -> Maybe a
Prelude> :t flip Data.Map.lookup
flip Data.Map.lookup :: Ord a => Data.Map.Map a a1 -> a -> Maybe a1
Prelude> let look = flip Data.Map.lookup
Loading package array-0.3.0.2 ... linking ... done.
Loading package containers-0.4.0.0 ... linking ... done.
Prelude> :t look
look :: Data.Map.Map () a -> () -> Maybe a
Why look
's inferred type differs from type of flip Data.Map.lookup
?
To give you some context. Initially I had small program and was trying to figure out why it produces compiler error:
import qualified Data.Map as M
type A = String
type B = String
data C = C1 | C2 | C3
deriving (Eq, Ord)
type D = String
z :: A -> M.Map A B -> M.Map B C -> M.Map C D -> Maybe D
z a aToB bToC cToD = look aToB a >>= look bToC >>= look cToD
where look = flip M.lookup
Ghci's reaction:
Prelude> :load main.hs
[1 of 1] Compiling Main ( main.hs, interpreted )
Failed, modules loaded: none.
main.hs:10:52:
Couldn't match expected type `C' with actual type `[Char]'
Expected type: C -> Maybe D
Actual type: A -> Maybe a0
In the return type of a call of `look'
In the second argument of `(>>=)', namely `look cToD'
I've found that this variation compiles well (type definitions are the same):
x :: A -> M.Map A B -> M.Map B C -> Maybe C
x a aToB bToC = look aToB a >>= look bToC
where look = flip M.lookup
y :: A -> M.Map A B -> M.Map B C -> M.Map C D -> Maybe D
y a aToB bToC cToD = (x a aToB bToC) >>= look cToD
where look = flip M.lookup
And after some experimentation it's turned up that if I put type of look
explicitly - first version compiles well too:
z :: A -> M.Map A B -> M.Map B C -> M.Map C D -> Maybe D
z a aToB bToC cToD = look aToB a >>= look bToC >>= look cToD
where look :: (Ord a) => M.Map a b -> a -> Maybe b
look = flip M.lookup
Which leads me to my first question.
By default, top-level bindings are non-polymorphic unless an explicit type specifier is given; this is known as the 'monomorphism restriction'. Since no type specifier was given, GHC had to choose a way to instantiate k
at the time you defined the function. It happened to choose k = ()
.
The idea behind this is that polymorphism can hurt performance by introducing a lot of vtable calls in the final compiled code; by forcing these to be resolved at compile time unless otherwise explicitly stated, this overhead can be avoided. This decision is rather controversial. GHC supports an extension to disable the monomorphism restriction entirely, by passing -XNoMonomorphismRestriction
.
这篇关于哈斯克尔的类型推断奇怪的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!