关于monomorphism restrictoin的问题

在看Haskell report其中关于monomorphism restriction产生的一些现象不是很理解。

我觉得monomorphism restriction是由于shared evaluation类型可能为多态而加入的。 比如(来自 haskell wiki)

import Data.List (genericLength)
f xs = let len = genericLength xs in (len, len) 

在 monomorphism restriction下,类型为Num t => [b] -> (t, t)

但是如果禁止monomorphism restriction 类型会为为 (Num t, Num t1) => [b] -> (t, t1)。这样就会计算长度2次。

但是,monomorphism restriction是如何影响eta化简的呢?又是怎么引起pattern match与lambda表达式有区别呢?

f x = show x      -- (合法) 
f = show         -- (不合法)

或者函数 g = (==)          -- (不合法) 
g x y = x == y               -- (合法) 
g = \x -> \y -> (x==y)     -- (不合法)

Submitted by xiaoxiaflash at a year ago

所有回复

首先,monomorphism restriction 并不影响所有的 eta 化简。比如:

g x = x
f = g

这里,f 和 g 的类型都被自动判定为 forall a . a -> a。而你给的例子里,show 的类型为 forall a . Num a => a -> String,这里的 a 属于受限制类型 (restricted type),不满足 monomorphism restriction 定义里 unrestricted 的定义,则 f = show 里面 f 的类型受到此规则限制,要作为单态对待。

而之所以会使用 monomorphism restriction 的原因,其一是你说的,为了防止意外情况下的重复计算。其二,是为了防止出现非法类型。比如 [(n,s)] = reads t 这个定义里,可以推出 s 的类型为 forall a . Show a => String,但是这个类型是非法类型,因为有歧义。因为这两个原因,才人为区分了 unrestricted 和 restricted 定义方式,(具体定义见 Haskell Report) 后者将会被当作单态处理,这样往往就不会影响类型的自动推导。比如

x = let f = show in f 1
y = let [(n,s)] = read "123.4" in show (n + 1)

都可以正常通过类型检查。所以,使用 monomorphism restriction 还有第三个好处:使用单态处理可以简化类型自动推导,让更多的合法程序能够通过类型检查。

而反对使用 monomorphism restriction 的人,也有他们的理由:

  1. 如果因为使用多态推导而引发意外的重复计算,可以给一个警告而不是简单地当作单态处理。
  2. 同样,对于歧议类型也应该给予警告,而不是简单当作单态处理。
  3. 使用了 monomorphism restriction 之后就算能够通过类型检查,但也并非万事大吉。比如上面我给的例子,计算 y 会引发动态错误报告,因为简单的单态推导会把 n 当作 Integer 而不是 Float 类型。把里面 1 改为 1.0 才勉强正确。

ninegua a year ago