2

我正在学习 SYB 和 rank n 类型,并遇到了一个令人困惑的情况,似乎是单态限制。

我编写了一个函数来查找与谓词匹配的最浅条目。我想接受一个更像谓词的函数Alternative,而不是归约函数,并自己将其转换为通用函数。我决定省略let块中的类型注释,以查看单态减少将如何影响此实现中的类型:

shallowest :: (Alternative f, Typeable b) => (b -> f a) -> GenericQ (f a)
shallowest p z =
  let op = (empty `mkQ` p) in
    op z <|> foldl (<|>) empty (gmapQ op z)

这会产生一个错误,表明let绑定中的歧义会阻止类型检查器解决约束Data a1

Error: • Couldn't match type ‘d’ with ‘a1’
  ‘d’ is a rigid type variable bound by
    a type expected by the context:
      forall d. Data d => d -> m a
  ‘a1’ is a rigid type variable bound by
    the type signature for:
      shallowest :: (b -> m a) -> GenericQ (m a)

(其他机构如根据“无法推断(Typeable a0)因使用'mkQ'而导致head (gmapQ op z)的绑定歧义”的行导致明确的错误let;我也没有弄清楚为什么上面的表格没有) .

let当我们在块中添加注释时,类型错误消失了op :: GenericQ (f a)(需要 ScopedTypeVariables)。

但是,我很困惑,似乎可以推断出Data约束:当它是返回类型时,以下类型检查:op

shallowest p = let { op = (empty `mkQ` p) } in op

有什么不同?两种情况都op需要forall d. Data d => d -> f a;我看到的唯一区别是第一个在参数位置,第二个在返回位置。

4

2 回答 2

2

在您的第二个片段中,op实际上不是多态的。

shallowest p = let { op = (empty `mkQ` p) } in op

这是一个微妙的区别:op实际上是单态的,但是在一个开放的上下文中。使用通常的打字判断符号,op右边的打字in看起来如下:

 types         values
 ↓             ↓
 x, a, f, ...; op :: x -> f a, ... |- op :: x -> f a
                                            ↑
                                            monotype (no "forall")

 In English: "op has type (x -> f a) in the context consisting of type variables (x, a, f, ...) and values (op :: x -> f a, ...)"

shallowest通过发生在顶层的泛化步骤使其具有多态性。如果在具有类型变量的上下文中x, a, f, ...,的主体shallowest具有类型x -> f a,那么我们可以“关闭上下文”并将类型变量移动到 的类型中shallowest :: forall x a f. x -> f a。类型推导如下所示:

     x, a, f |- (let op = ... in op) :: x -> f a
 ⸻⸻⸻⸻⸻⸻⸻⸻⸻⸻⸻⸻⸻ (generalization)
   |- (let op = .... in op) :: forall x a f. x -> f a

(类型类和统一算法使事情变得更加复杂,但这不是这个答案的重点。)

使用多态进行类型检查的主要问题是决定何时进行泛化。由于缺乏主要类型和不确定性,没有通用的解决方案。所以类型检查器的实现必须做出一些选择。

在 Haskell 中,泛化发生在以下位置(列表可能并不详尽),这是相当自然的选择:

  • 函数定义,即let具有至少一个显式参数的顶层绑定(这里是单态限制);

  • 高阶函数的多态参数:如果你有一个函数f :: (forall a. w a) -> r,那么在类型检查时f x会进行泛化;ax

  • 当然,当由显式注释指示时_ :: forall a. t a

于 2019-05-26T17:33:49.057 回答
0

初步说明:鉴于此处提供的证据,我假设您正在使用:

  • type GenericQ r = forall a . Data a => a -> r syb
  • gmapQ :: Data a => (forall d. Data d => d -> u) -> a -> [u] Data.Data.

如果我对此有误,请告诉我。此外,forall下文中的任何 s 都将被明确写入。


这里有很多东西。正如夏立耀所暗示的,这是一个涉及类型的概括问题op。关于您对 的第一个定义,有三个相关事实shallowest

  1. 在泛化之前,推断的类型opData d => d -> f a。鉴于Data d约束,单态限制的规则 1(参见报告的第 4.5.5 小节)意味着d这种类型不能被概括。

  2. 在 的正文中shallowestop出现在两个地方。第一个是op zz :: a1在顶层被 的签名约束和约束shallowest。结果是,这种出现不需要op参数类型的泛化:就它而言,类型可以是,类型变量中的单态(我从报告的第 4.5.4 小节中采用了这个术语)。opforall f a. a1 -> f aa1

  3. 然而,另一个事件是gmapQ op zgmapQ具有 rank-2 类型,需要多态参数。既然如此,这种情况需要对 的论点类型进行概括op,正如夏立耀的回答末尾所指出的那样。

#1 和 #3 是相互矛盾的要求,因此您会遇到类型错误,这可以通过禁用单态限制或通过要求op对带有签名的参数类型进行多态来避免。由于op#2 中描述的另一个事件,这种情况被报告为涉及这两个事件的不匹配。


下面是一个更简单的扩展示例,它可能有助于了解发生了什么。(如果您要将以下代码片段放入 GHCi,此外-XRankNTypes您还应该设置-XMonomorphismRestrictionand-XNoExtendedDefaultRules以查看相同的结果。)

这是一个 rank-2 类型的函数,它将扮演以下角色gmapQ

glub :: (forall x. Show x => x -> String) -> String
glub f = f 7

现在让我们尝试一个类似于shallowest...的场景

foo1 :: forall a. Show a => a -> String
foo1 x = bar x ++ glub bar
  where
  bar = show

...还有你的错误:

<interactive>:506:23: error:
    • Couldn't match type ‘x’ with ‘a’
      ‘x’ is a rigid type variable bound by
        a type expected by the context:
          forall x. Show x => x -> String
        at <interactive>:506:18-25
      ‘a’ is a rigid type variable bound by
        the type signature for:
          foo1 :: forall a. Show a => a -> String
        at <interactive>:505:1-38
      Expected type: x -> String
        Actual type: a -> String
    • In the first argument of ‘glub’, namely ‘bar’
      In the second argument of ‘(++)’, namely ‘glub bar’
      In the expression: bar x ++ glub bar
    • Relevant bindings include
        bar :: a -> String (bound at <interactive>:508:3)
        x :: a (bound at <interactive>:506:5)
        foo1 :: a -> String (bound at <interactive>:506:1)

在应该去的签名处添加一个通配符bar会产生一个额外的错误,这个错误更具暗示性:

foo2 :: forall a. Show a => a -> String
foo2 x = bar x ++ glub bar
  where
  bar :: _
  bar = show
• Found type wildcard ‘_’ standing for ‘a -> String’
  Where: ‘a’ is a rigid type variable bound by
           the type signature for:
             foo2 :: forall a. Show a => a -> String
           at <interactive>:511:1-38
  To use the inferred type, enable PartialTypeSignatures
• In the type signature: bar :: _
  In an equation for ‘foo2’:
      foo2 x
        = bar x ++ glub bar
        where
            bar :: _
            bar = show
• Relevant bindings include
    x :: a (bound at <interactive>:512:5)
    foo2 :: a -> String (bound at <interactive>:512:1)

请注意通配符“代表a -> String”是如何被声明为一个独立的事实,a而不是受foo2. 我相信这对应于我在上面第 2 点中提到的类型变量中的单态和多态之间的区别。

提供bar多态类型签名使其工作:

foo3 :: forall a. Show a => a -> String
foo3 x = bar x ++ glub bar
  where
  bar :: forall b. Show b => b -> String
  bar = show

使 bar 的定义变得有意义也是如此,它通过使其成为“函数绑定”而不是“简单模式绑定”来规避单态性限制:

foo4 :: forall a. Show a => a -> String
foo4 x = bar x ++ glub bar
  where
  bar x = show x

为了完整起见,值得注意的是,没有类型限制意味着没有单态限制:

foo5 :: forall a. Show a => a -> String
foo5 x = bar x ++ glub bar
  where
  bar = const "bar"

相关情况涉及使用bar两次,但没有 rank-2 函数:

foo6 x y = bar x ++ bar y
  where
  bar = show

GHC 会推断出哪种类型foo6

GHCi> :t foo6
foo6 :: Show a => a -> a -> [Char]

参数获得相同的类型,否则需要对 进行泛化bar,这需要类型签名(或 pointfullness 等):

foo7 x y = bar x ++ bar y
  where
  bar :: forall a. Show a => a -> String
  bar = show
GHCi> :t foo7
foo7 :: (Show a1, Show a2) => a1 -> a2 -> [Char]

由于我还没有提到它,这里是你的第二个类似物shallowest

foo8 :: forall a. Show a => a -> String 
foo8 x = bar x
  where
  bar = show

值得强调的bar是,这里实际上并没有被概括:它在类型变量中是单态的a。我们仍然可以通过弄乱foo7而不是使用来打破这个例子bar

foo9 = bar
  where
  bar :: _
  bar = show

在这种情况下,bar不是通用的,也不是foo(现在无点且没有签名)。这意味着单态类型变量永远不会被解析。根据单态限制的规则 2,它变成了一个模棱两可的类型变量:

    <interactive>:718:14: error:
        • Found type wildcard ‘_’ standing for ‘a0 -> String’
          Where: ‘a0’ is an ambiguous type variable
          To use the inferred type, enable PartialTypeSignatures
        • In the type signature: bar :: _
          In an equation for ‘foo9’:
              foo9
                = bar
                where
                    bar :: _
                    bar = show
        • Relevant bindings include
            foo9 :: a0 -> String (bound at <interactive>:716:5)

<interactive>:719:13: error:
    • Ambiguous type variable ‘a0’ arising from a use of ‘show’
      prevents the constraint ‘(Show a0)’ from being solved.
      Relevant bindings include
        bar :: a0 -> String (bound at <interactive>:719:7)
        foo9 :: a0 -> String (bound at <interactive>:716:5)
      Probable fix: use a type annotation to specify what ‘a0’ should be.
      These potential instances exist:
        instance Show a => Show (ZipList a)
          -- Defined in ‘Control.Applicative’
        instance Show Constr -- Defined in ‘Data.Data’
        instance Show ConstrRep -- Defined in ‘Data.Data’
        ...plus 64 others
        ...plus 250 instances involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    • In the expression: show
      In an equation for ‘bar’: bar = show
      In an equation for ‘foo9’:
          foo9
            = bar
            where
                bar :: _
                bar = show

bar在定义中添加类型签名foo9将无济于事——它只会改变报告错误的点。更改bar为没有约束的东西确实消除了错误,因为它可以概括barfoo

于 2019-05-27T02:55:44.977 回答