Lambda函数的矛盾行为

Question

使用以下定义：

lenDigits n = length (show n)
factorial n = product [1..n]

我评估以下内容

Prelude> ((lenDigits . factorial) 199) <= 199
False
Prelude> (\i -> ((lenDigits . factorial) i) <= i) 199
True

为什么会出现这样的行为？在我看来，第一个表达式只是将lambda缩减后与第二个表达式完全相同。

- Agnishom Chattopadhyay

---

您可能会喜欢比较这两者，这可以涉及到问题的本质，并避免在周围存在类型类以混淆事情的所有模糊性：(id True, id 'a') 是可以接受的，但 (\f -> (f True, f 'a')) id 是错误的。 - Daniel Wagner

@DanielWagner 为什么会发生这种情况？id 不是具有多态性吗？ - Agnishom Chattopadhyay

确实，id 是多态的；而 \f -> ... 也可以是多态的；但是在 ... 中，f 本身不是 多态的！\f -> (f True, f 'a') 即使没有提到 id，它已经是一个类型错误了。这个限制是为了让类型推导更容易，并保持任何能够被赋予类型的术语都具有最一般类型的可取性质。 - Daniel Wagner

Answer 1

因为在第一个表达式中，第一个 199 的类型为 Integer，而第二个的类型为 Int。但在第二个表达式中，两者都是 Int 类型，factorial 199 无法用 Int 类型表示。

- freestyle

---

这与单态限制有关吗？ - mnoronha

我不这么认为。在第一个例子中，前面的199可以默认为“整数类型”，但是后面的199由于要与lenDigits的返回值进行比较，所以被强制转换为Int类型。在第二个例子中，同样的原因，变量i也被强制转换为Int类型，然后又强制将199转换为Int类型。 - chepner

length 的返回类型为什么不是多态的？ - mnoronha

@mnoronha 是的，例如性能。但是你可以使用genericLength :: Num i => [a] -> i。 - freestyle

@mnoronha 请参考SE.SE上的文章：为什么`length`默认不是泛型？。 - duplode

Answer 2

这里是一步一步的解答这个问题。

首先，让我们从以下开始：

((lenDigits . factorial) 199) <= 199

根据Haskell报告，整数字面量表示对类型为Integer的相应值应用函数fromInteger。这意味着我们的第一个表达式实际上是：

((lenDigits . factorial) (fromInteger (199 :: Integer)) 
    <= (fromInteger (199 :: Integer))

fromInteger (199 :: Integer)本身具有多态类型Num a => a。现在我们需要看看这种类型在整个表达式的上下文中是否被专门化。请注意，除非我们找到它不是这样的理由，否则我们应该假设两个fromInteger (199 :: Integer)的多态类型是独立的（如果您愿意，它们是Num a => a和Num b => b）。 lenDigits的类型是Show a => a -> Int，因此...

(lenDigits . factorial) (fromInteger (199 :: Integer))

<= 左侧必须是一个 Int。鉴于 (<=) 是 Ord a => a -> a -> Bool 类型，<= 右侧的 fromInteger (199 :: Integer) 也必须是一个 Int。整个表达式如下：

((lenDigits . factorial) (fromInteger (199 :: Integer)) <= (199 :: Int)

虽然第二个199是专门针对Int的，但第一个仍然是多态的。在没有其他类型注释的情况下，默认情况下在GHCi中使用表达式时，它将特化为Integer。因此，我们最终得到：

((lenDigits . factorial) (199 :: Integer)) <= (199 :: Int)

现在，我们来看第二个表达式：

(\i -> ((lenDigits . factorial) i) <= i) 199

按照上面使用的同样的推理，(lenDigits . factorial) i（在<=左侧）是一个Int，因此i（在<=右侧）也是一个Int。既然如此，我们有...

GHCi> :t \i -> (lenDigits . factorial) i <= i
\i -> (lenDigits . factorial) i <= i :: Int -> Bool

因此，将其应用于199（实际上是fromInteger（199 :: Integer））会将其特化为int，结果为：

((lenDigits . factorial) (199 :: Int)) <= (199 :: Int)

现在的第一个 199 已经是 Int 而不是 Integer 了。对于固定大小的 Int 类型，factorial (199 :: Int) 会溢出，导致错误的结果。避免这种情况的一种方法是引入显式的 fromInteger，以获得类似于第一个场景的东西：

GHCi> :t \i -> (lenDigits . factorial) i <= fromInteger i
\i -> (lenDigits . factorial) i <= fromInteger i :: Integer -> Bool
GHCi> (\i -> (lenDigits . factorial) i <= fromInteger i) 199
False

- duplode