9

下面是几个简单的函数：

f1 :: () -> ()
f1 () = ()

f2 :: a -> a
f2 a = a

f3 :: a -> (a, a)
f3 a = (a, a)

f4 :: (a, b) -> a
f4 (a, b) = a

所有f1、f2和f3都能够接受()作为输入。另一方面，当然f4不能接受()；f4 ()是类型错误。

是否有可能从类型理论上描述f1、f2和f3的共同点？具体来说，是否可以定义一个acceptsUnit函数，使得acceptsUnit f1、acceptsUnit f2和acceptsUnit f3是类型良好的，但是acceptsUnit f4是类型错误——并且没有其他影响？

以下内容完成了部分工作，但将其输入单态化（在 Haskell 中，我在 Hindley-Milner 中收集），因此其效果不仅仅是断言其输入可以接受()：

acceptsUnit :: (() -> a) -> (() -> a)
acceptsUnit = id

-- acceptsUnit f4     ~> error 
-- acceptsUnit f3 'a' ~> error ☹️

当然，同样的单态化也发生在下面。在这种情况下，注解的类型acceptsUnit'是它的主要类型。

acceptsUnit' :: (() -> a) -> (() -> a)
acceptsUnit' f = let x = f () in f
4

1 回答 1

3

很容易从类型理论上描述什么f1,f2和f3没有f4共同点。在 Hindley-Milner 的语言中，前三个具有可以专门化为以下形式的多型的多型：

forall a1...an. () -> tau

对于 n >= 0 和 tau 任意单型。第四个不行。

你能写一个接受前三个作为参数但拒绝第四个的函数吗？好吧，这取决于您使用的类型系统以及构建函数的范围。在通常的 Hindley-Milner 和/或标准 Haskell 类型系统中，如果您可以将候选函数的两个副本传递给接受函数，则以下内容将起作用：

acceptsUnit :: (() -> a) -> (b -> c) -> (b -> c)
acceptsUnit = flip const

f1 :: () -> ()
f1 () = ()

f2 :: a -> a
f2 a = a

f3 :: a -> (a, a)
f3 a = (a, a)

f4 :: (a, b) -> a
f4 (a, b) = a

main = do
  print $ acceptsUnit f1 f1 ()
  print $ acceptsUnit f2 f2 10
  print $ acceptsUnit f3 f3 10
  -- print $ acceptsUnit f4 f4  -- type error

这可能是您使用标准 Haskell 可以做到的最好的事情（并且可能是使用 Haskell 和 GHC 类型系统扩展可以做到的最好的事情，或者有人现在已经找到了一些东西）。

如果您可以使用自己的打字规则自由定义自己的打字系统，那么天空就是极限。

于 2021-07-29T19:16:52.427 回答