有意地在Haskell中定义无限类型

Question

我想定义一个似乎需要无限类型的东西。

要求：定义一个函数“eat”，它吃掉所有参数，除了数字“3”，对于数字“3”，它返回3。

eat 3 = 3
eat x = eat

所以基本上像“eat (+) foldl (Just 5) 3”这样的任意表达式将计算为3。但是问题在于eat的类型。它应该是什么？

我得到的最接近可运行代码是：

newtype Rec = MakeRec (Int -> Rec)

eat :: Int -> Rec
eat x = MakeRec eat


instance Show Rec where
     show _ = "EAT"

这对于"eat 6"可以正常工作，但是对于"eat 6 7"则不能工作，并且如果我在定义中放置(eat 3=3)，它也不起作用。

我不确定在Haskell中是否可能实现这一点。(有什么参数可以用来证明它是不可能的?)

更新：如下面的解决方案中所述，编译时需要类型信息，以便编译器知道"eat foldl 3 foldl"是否无效。因此，该问题的确切解决方案是不可能的。

- Karan

Answer 1

这是不可能的。在Haskell中，显式禁止无限类型（不是数据类型），而且很容易生成需要这些类型的代码，从而产生错误（例如，尝试使用 let foo = (42, foo) in foo）。

当然，您可以像您所做的那样使用newtype和data创建它们，但是然后您必须明确地包装和解包构造函数中的值。

这是一个明确的设计决策：对于无限类型，我们希望编译器拒绝许多明显错误的表达式必须允许，并且由于许多程序将被允许，因此以前一些明确类型化的程序将变得模棱两可，需要显式类型注释。因此做出了一个权衡：要求您在返回中明确指定相当罕见的无限类型，以换取比我们否则所能得到的类型系统更多的帮助。

话虽如此，确实有一种方法可以使用类型类定义与您的eat函数类似的东西，但它不能仅在您给它3个时停止：是否已经给它3个只能在运行时确定，并且类型在编译时确定。但是，这里有一个过载值，既可以是Integer，也可以是刚刚消耗其参数的函数：

class Eat a where
    eat :: a

instance Eat Integer where
    eat = 3

instance (Eat r) => Eat (a -> r) where
    eat _ = eat

关键在于您需要在使用它时精确地指定类型：

*Main> eat 1 foldr ()

<interactive>:6:1:
    Ambiguous type variable `t0' in the constraint:
      (Eat t0) arising from a use of `eat'
    Probable fix: add a type signature that fixes these type variable(s)
    In the expression: eat 1 foldr ()
    In an equation for `it': it = eat 1 foldr ()
*Main> eat 1 foldr () :: Integer
3

这是因为 eat 1 foldr () 可能是一个Integer，但它也可能是另一个函数，就像我们在同一表达式中使用 eat 1 和 eat 1 foldr 一样。再次，我们获得了灵活的类型，但必须明确指定我们想要返回的类型。

¹ 考虑类型类重载，就像重载数字字面量（42 可以是任何实现了 Num 的类型）。

- ehird

---

Haskell 中没有无限类型是可以的。我想知道是否有一种解决方法，在这里不会 技术上 使用无限类型，但仍然有效。 - Karan

我可以这样编写代码："eat n = n"，其中n是一个数字，"eat _ = eat"表示其他情况下都返回eat。这样，在编译时，"eat 2 foldl"会被判定为错误，因为它会被计算成"2 foldl"，而"eat foldl 2"则会正确地计算出2。 - Karan

从技术上讲，可以以这种方式特殊处理Integer参数，但它必须使用相当脆弱和非常神秘的类型黑客（TypeEq），并且由于数字重载，它必须是eat (2 :: Integer) foldl。 - ehird

我怀疑我不会很快深入研究这个TypeEq的东西 :)。 - Karan

我希望我们可以像写“id id id 3”并且它会计算出3一样，我们也能够使用“eat”（其中eat是id的激进表亲）。 - Karan