Haskell 中的类型类和类型推断

Question

我正在尝试弄清楚类型推断是如何与类型 classes 一起工作的，但到目前为止还很难完全掌握它。

让我们定义以下简单的 HList:

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE ScopedTypeVariables #-}

infixr 6 :::

data HList xs where
  HNil :: HList '[]
  (:::) :: a -> HList as -> HList (a ': as)

现在我要定义 class 类型，允许 "uncurry" 任何函数转换为 HList:

类型的单个参数的函数

class FnToProduct fn ls out | fn ls -> out where
  fromFunction :: fn -> HList ls -> out

instance (FnToProduct' (IsArity1 fn) fn ls out) => FnToProduct fn ls out where
  fromFunction = fromFunction' @(IsArity1 fn)

class FnToProduct' (arity1 :: Bool) fn ls out | fn ls -> out where
  fromFunction' :: fn -> HList ls -> out

instance FnToProduct' True (input -> output) '[input] output where
  fromFunction' fn (a ::: tail) = fn a

instance (FnToProduct fnOutput tail out') => FnToProduct' False (input -> fnOutput) (input ': tail) out' where
  fromFunction' fn (input ::: tail) = fromFunction (fn input) tail

type family IsArity1 fn where
  IsArity1 (a -> b -> c) = False
  IsArity1 (a -> b) = True

现在我要破解编译了：

test = fromFunction (\a b -> a) (True ::: False ::: HNil)

• Ambiguous type variables ‘p0’, ‘p1’,
                               ‘out0’ arising from a use of ‘fromFunction’
      prevents the constraint ‘(FnToProduct'
                                  'False (p1 -> p0 -> p1) '[Bool, Bool] out0)’ from being solved.
        (maybe you haven't applied a function to enough arguments?)
      Relevant bindings include test :: out0 (bound at src/HList.hs:98:1)
      Probable fix: use a type annotation to specify what ‘p0’, ‘p1’,
                                                          ‘out0’ should be.
      These potential instance exist:
        one instance involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    • In the expression:
        fromFunction (\ a b -> a) (True ::: False ::: HNil)
      In an equation for ‘test’:
          test = fromFunction (\ a b -> a) (True ::: False ::: HNil)
   |
98 | test = fromFunction (\a b -> a) (True ::: False ::: HNil)
   |        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

但是如果我明确指定函数类型：

test = fromFunction (\(a :: Bool (b :: Bool) -> a) (True ::: False ::: HNil)

效果很好。我如何在此处强制执行类型推断，以便编译器选择 HList 的类型来找出函数中的类型？到目前为止，我还尝试使用 infixl/r 运算符但没有任何运气。

Answer 1

类型类是 "matchy"。在你的例子中，GHC 说它正在尝试解决约束

FnToProduct' 'False (p1 -> p0 -> p1) '[Bool, Bool] out0

其中统一变量 p1 和 p0 来自第一个参数的隐式扩展：

(\(a :: _p1) (b :: _p0) -> a)

和来自 fromFunction 类型的统一变量 out0。本质上，GHC 不知道参数类型应该是什么，也不知道 fromFunction 调用最终应该是什么 return，因此它创建了三个变量来表示它们并试图弄清楚它们应该是什么。

没有 instance 匹配此约束。

instance _ => FnToProduct' False (input -> fnOutput) (input ': tail) out'

会要求 p1 和 Bool 相同，但它们不是。它们可能是，正如您在带类型注释的示例中所展示的那样，但 GHC 认为它们没有是。你可以想象添加

instance _ => FnToProduct' False (Int -> fnOutput) (Bool ': tail) out'

现在你不知道是 a :: Int 还是 a :: Bool，因为这两个实例都是 "fit"。但是，在开放世界的假设下，您必须假设可以随时添加这样的新实例。

一种解决方法是使用 ~ 约束：

instance (i ~ i', o ~ o') => FnToProduct' True (i -> o) '[i'] o'
instance (i ~ i', FnToProduct r t o) => FnToProduct' False (i -> r) (i' ': t) o

第二个实例现在匹配，因为两个 i 变量不同。它现在实际上指导类型推断，因为 i ~ i' 要求，在这种情况下，转换为 p1 ~ Bool 要求，用于实例化 p1 . p0 也是如此。

或者，添加另一个功能依赖项。这并不总是有效，但它似乎在这里完成了工作

class FnToProduct fn ls out | fn ls -> out, fn out -> ls
class FnToProduct' (arity1 :: Bool) fn ls out | fn ls -> out, fn out -> ls

这告诉 GHC fs（因此它的参数类型，这里是 p1 和 p0）可以从 ls（这里是 [Bool, Bool]).

除此之外，我认为您的函数可以简化为：

class AppHList ts o f | ts f -> o, ts o -> f where
   appHList :: f -> HList ts -> o
instance AppHList '[] o o where
   appHList x HNil = x
instance AppHList ts o f => AppHList (t : ts) o (t -> f) where
   appHList f (x ::: xs) = appHList (f x) xs

人为地要求 HList 提供所有参数并不是特别有用，而且它在多态上下文中确实会爆炸，因为您通常无法分辨 "supplying all the arguments" 应该是什么意思。例如。 const 可以有任意数量的参数，从 2 个开始。因此，appHList const (id ::: 'a' ::: HNil) 6 有效（其中 const 有 3 个参数），但 fromFunction 在该上下文中失败。

如果您确实需要，您仍然可以将 "returns a not-function" 属性从外部强加到更有用的函数。

type family IsFun f :: Bool where
  IsFun (_ -> _) = True
  IsFun _ = False
fullAppHList :: (IsFun o ~ False, AppHList ts o f) => f -> HList ts -> o
fullAppHList = appHList

Answer 2

这里有一个选项：

class (f ~ AbstractList ts o) => AppHList ts o f where
  appHList :: f -> HList ts -> o

type family AbstractList xs o where
  AbstractList '[] o = o
  AbstractList (x ': xs) o =
    x -> AbstractList xs o

instance f ~ o => AppHList '[] o f where
  appHList x HNil = x

instance (AppHList ts o f', f ~ (t -> f'))  => AppHList (t ': ts) o f where
  appHList f (x ::: xs) = appHList (f x) xs

虽然只有一个等式约束，但这表达了几个方向的依赖关系。怎么样？关键是一旦知道列表的结构，类型族就可以减少；第二个参数不需要任何内容，也需要 none 个列表元素。

这似乎与HTNW的简化版具有相同的推理能力，但它有两个优点：

如果需要，可以得到平等证据。
与 PartialTypeSignatures 扩展一起使用效果更好。由于某种原因，GHC 似乎在这种情况下绊倒了 fundep 版本。见 this ticket 我刚刚提交。

但是等等！还有更多！这个公式表明即使 class 也是可选的！当一切都专门化和完全内联时，基于 class 的方法可能是最有效的，但这个版本看起来简单得多：

appHList' :: f ~ AbstractList ts o => f -> HList ts -> o
appHList' x HNil = x
appHList' f (x ::: xs) = appHList' (f x) xs

Haskell 中的类型类和类型推断

Typeclasses and type inference in Haskell

haskell

type-inference

typeclass