如何从范围内的约束族派生类型类实例？

Question

编辑： 我跟进了更多。谢谢这里的回答者，我认为后续问题更好地解释了我在这里介绍的一些困惑。

TL;DR 我正在努力将约束证明放入表达式中，同时使用对构造函数具有存在约束的 GADT。（这是一个严重的一口，抱歉！）

我将问题归结为以下几点。我有一个简单的 GADT，它表示称为 X 的点和称为 F 的函数应用程序。点 X 被限制为 Objects.

data GADT ix a where
  X :: Object ix a => a -> GADT ix a
  F :: (a -> b) -> GADT ix a -> GADT ix b

Constrained指的是对象受something约束的容器，Object就是something。（编辑： 我真正的问题涉及 Category 和 Cartesian classes 来自 constrained-categories）

-- | I can constrain the values within containers of kind `* -> *`
class Constrained (ix :: * -> *) where
  type Object ix a :: Constraint

-- | Here's a trivial constraint. A more interesting one might include `Typeable a`, for ex
instance Constrained (GADT ix) where
  type Object (GADT ix) a = (Constrained ix, Object ix a)

我要写一个表达式：

-- error: Could not deduce: Object ix Int arising from a use of ‘X’
ex0 :: GADT ix String
ex0 = F show (X (3 :: Int))

虽然显而易见的解决方案有效，但在构建更大的表达式时它很快就会变得冗长：

-- Typechecks, but eventually verbose
ex1 :: Object ix Int => GADT ix String
ex1 = F show (X (3 :: Int))

我认为正确的解决方案应该是这样的：

-- error: Could not deduce: Object ix Int arising from a use of ‘X’
ex2 :: Constrained ix => GADT ix String
ex2 = F show (X (3 :: Int))

但我仍然无法得到 Object ix Int 的证明。

我相信这比我想象的要简单。我尝试在 GADT class 实例中向 Object 约束系列添加约束。我试过在表达式的签名中提供约束。我试过 QuantifiedConstraints，不过，我不确定我是否完全掌握了它。请高手帮帮我！

可运行：

{-# LANGUAGE GADTs #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE QuantifiedConstraints #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeFamilyDependencies #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE InstanceSigs #-}

module Test where

import Data.Kind
import Data.Functor.Identity
import Data.Functor.Const

-- | I can constrain the values within containers of kind `* -> *`
class Constrained (ix :: * -> *) where
  type Object ix a :: Constraint

-- | Here's a trivial constraint. A more interesting one might include `Typeable a`, for instance
instance Constrained (GADT ix) where
  type Object (GADT ix) a = (Constrained ix, Object ix a)

-- | A demo GADT that has function application ('F'), and points ('X'). The
-- points are constrained.
data GADT ix a where
  X :: Object ix a => a -> GADT ix a
  F :: (a -> b) -> GADT ix a -> GADT ix b

-- -- Broken
-- -- error: Could not deduce: Object ix Int arising from a use of ‘X’
-- ex0 :: GADT ix String
-- ex0 = F show (X (3 :: Int))

-- Typechecks
-- but for larger programs becomes verbose, requiring many explicit constraints
ex1 :: Object ix Int => GADT ix String
ex1 = F show (X (3 :: Int))

-- -- What I want, but, it's broken
-- ex2 :: Constrained ix => GADT ix String
-- ex2 = F show (X (3 :: Int))

Answer 1

I think the correct solution should look something like this:
-- error: Could not deduce: Object ix Int >arising from a use of ‘X’
ex2 :: Constrained ix => GADT ix String
ex2 = F show (X 3)

不幸的是，这个解决方案没有任何意义。编译器有理由指出它不知道此时 Object ix Int 是否满足，因为它只知道 Constrained ix 可能会施加某些约束通过 Object ix Int.

量化解决

所以也许你想要的是一个约束，它说：“在这一点上，我使用的所有 Object ix a 约束都得到满足”——我们可以尝试通过量化来做到这一点：

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ConstraintKinds #-}

type Satisfied ix = forall a. Object ix a

ex2 :: Satisfied ix => GADT ix String
ex2 = F show (X 3)

不幸的是，这给了我们一个 GHC 错误：

• Quantified predicate must have a class or type variable head:
        forall a. Object ix a
• In the quantified constraint ‘forall a. Object ix a’
  In the type synonym declaration for ‘Satisfied’

因为 Object 是类型族而不是 class 或类型变量。

重新架构

但是...为什么 Object 是一个类型家族？事实上，为什么Constrained会作为一个没有办法的无法无天的class存在呢？如果我们想对容器和类型的组合施加约束，Haskell 已经为我们提供了这样做的方法 - 只需使用实例约束！

{-# LANGUAGE MultiParamTypeClasses #-}

class Object ix a

type Constrained ix = forall a. Object ix a

因为如果我们有

instance (...<some stuff>...) => Constrained Foo where
  type Object ix a = (...<some def>...)

我们可以将其翻译成

instance (...<some stuff>..., ...<some def>...) 
  => Object ix a

这使得这个例子编译。

ex2 :: Constrained ix => GADT ix String
ex2 :: F show (X 3)

Answer 2

在没有更多上下文的情况下，很难说什么是最好的解决方案，但这里有几种可能性：

完全避免约束

就目前而言，您的 GADT 似乎没有太多理由将 X 限制为 Object。也许这只是不需要？

data GADT ix a where
  X :: a -> GADT ix a
  F :: (a -> b) -> GADT ix a -> GADT ix b

相反，约束可以在需要时来自外部。

咬住约束列表的子弹，但让它们更好

如果你的表达式中有许多不同的类型都需要满足相同的约束，你可以使用像 All

这样的助手

ex2' :: All (Object ix) '[Int] => GADT ix String
ex2' = F show (X (3 :: Int))

除了Int之外，列表中还可以有更多的类型； and/or 您可以进行同义词约束，例如

type StdObjs ix = (Object ix Int, Object x Bool, ...)

ex2'' :: StdObjs ix => GADT ix String
ex2'' = F show (X (3 :: Int))

通过数据结构本身向后传播约束

如果您确实需要对 X 值的约束，则可以在 GADT 中以另一种方式表达这一点。例如，如果函数不是通用函数，而是已经被限制为仅接受 Objects 的函数，您可以这样设置：

data YourFunc ix a b where
  YourFunc :: Object ix a => (a->b) -> YourFunc ix a b

show' :: Object ix Int => YourFunc ix Int String
show' = YourFunc show

这并不能直接帮助解决您所询问的问题，但也许该功能是共享的或其他原因。你甚至可以有类似

的东西

class Object ix a => InferrenceChain ix a where
  type PreElem ix a :: Type
  propInferrence :: (InferrenceChain ix (PreElem a) => r) -> r

然后

data YourFunc ix a b where
  YourFunc :: InferrenceChain ix a
                 => (PreElem a -> a) -> YourFunc (PreElem a) a

然后最后你可以证明 X 约束只是在外部放入 Object ix String 并递归 propInferrence。但这可能会变得非常繁琐。

如何从范围内的约束族派生类型类实例？

How can I derive typeclass instances from constraint families that are in scope?

haskell

constraints

existential-type

gadt

quantified-constraints

量化解决

重新架构

完全避免约束

咬住约束列表的子弹，但让它们更好

通过数据结构本身向后传播约束