Транзитивный класс Subset для наборов уровней типов

Question

Я работаю с библиотекой наборов уровней Доминика Орчарда , которая очень внимательно следует его статье . Я столкнулся с ситуацией, когда у меня есть контексты, предоставляющие Subset s t а также Subset t v, и мне нужно, чтобы GHC каким-то образом понимал, что это подразумевает Subset s v. Но такого экземпляра нет.

Как я могу представить транзитивность «подмножества» для целей наборов уровня типа?

Я пробовал просто добавить

      instance {-# OVERLAPS #-} (Subset s t, Subset t v) => Subset s v where
  subset xs = subset (subset xs :: Set t)

в мой рабочий файл (видимо Subsetне закрытый мир; Я думаю , что ); это дает множество различных сообщений об ошибках в зависимости от того, какие параметры компилятора я использую, или если я заменяю OVERLAPS для INCOHERENT. Суть в том, что GHC не может выбрать экземпляр для использования, даже если я обещаю, что все будет в порядке.

Кажется маловероятным, что это невозможно, но я застрял в этом на день, и я не в себе.

Answer 1

Пока что лучшее решение, которое мне удалось придумать, - это Ghosts of Departed Proofs, с помощью которого я могу переместить логику подмножеств из системы типов. Это немного неуклюже, и я совсем не уверен, что использую его правильно.

Subset.hs

      module Subset (
  immediateSubset,
  Subset,
  SubsetProof,
  transitiveSubset,
  unionOfSubsets
) where

import Data.Type.Set (Subset, Union)
import Logic.Classes (Transitive, transitive)
import Logic.Proof (axiom, Proof, sorry)

data Subset' s t where {}
instance Transitive Subset' where {}
type SubsetProof s t = Proof (Subset' s t)

immediateSubset :: (Subset s t) =>
                   SubsetProof s t
immediateSubset = axiom
transitiveSubset :: forall k (s :: [k]) (t :: [k]) (v :: [k]).
                    SubsetProof s t -> SubsetProof t v -> SubsetProof s v
transitiveSubset = transitive
unionOfSubsets :: forall k (s1 :: [k]) (s2 :: [k]) (t :: [k]).
                  SubsetProof s1 t -> SubsetProof s2 t -> SubsetProof (Union s1 s2) t
unionOfSubsets s1t s2t = sorry

Lib.hs

      module Lib {-()-} where

import Data.Type.Nat (Nat)
import Data.Type.Set (IsSet)
import Polysemy (Sem, makeSem, reinterpret)

import Subset (immediateSubset, Subset, SubsetProof, transitiveSubset)


data Located (parties :: [Nat]) v = Located v

data Com (parties :: [Nat]) m a where
  SendInt :: forall recipients senders parties m.
             SubsetProof recipients parties 
             -> SubsetProof senders parties
             -> Located senders Int
             -> Com parties m (Located recipients Int)
  FromUniversal :: forall parties m a.
                   Located parties a -> Com parties m a

-- Polysemy uses template haskell:
makeSem ''Com
--sendInt :: Member (Com parties) r => (Located senders Int) -> Sem r (Located recipients Int)
--fromUniversal :: Member (Com parties) r => (Located parties a) -> Sem r a
--we can manually write out the functions instead of useing makeSem;
--that might help make Located's type artument explicit, but I don't think it matters here.

-- "lift" a program in a small community (clique) into a larger community's monad. 
runClique :: forall parties clq r a.
          (IsSet parties,
           IsSet clq,
           Subset clq parties) =>
          Sem (Com clq ': r) a
          -> Sem (Com parties ': r) (Located clq a)
runClique = (Located <$>) . (reinterpret _clique)
  where cp = immediateSubset :: SubsetProof clq parties
        _clique :: forall rInitial x.
                   Com clq (Sem rInitial) x -> Sem (Com parties ': r) x
        _clique (SendInt rc sc x) = sendInt (transitiveSubset rc cp) (transitiveSubset sc cp) x
        _clique (FromUniversal (Located v)) = return v

Answer 2

GHC Haskell действительно поддерживает транзитивность только для двух типов ограничений:

1. (Номинальные) ограничения равенства

           (a ~ b, b ~ c) => a ~ c
   

2. Ограничения репрезентативного равенства

           (Coercible a b, Coercible b c) => Coercible a c
   

Эти правила (очень тщательно) встроены в процесс разрешения ограничений для совершенно волшебного ~и ограничения; в языке ограничений нет другой транзитивности. Основная проблема заключается в том, что если у вас есть класс

      class C a b

и ты пишешь

      instance (C a b, C b c) => C a c

тогда неоднозначно. Когда GHC пытается решить C a c, он понятия не имеет, что вы хотите. В настоящее время у пользователя нет способа указать, какой bиспользовать там, где требуется ограничение, поэтому экземпляр действительно нельзя использовать.

The Subsetвведите Data.Type.Setне похоже на равенство или Coercibleограничение, поэтому вы просто не можете этого сделать.

Существуют ли другие способы выразить идею о том, что список является подмножеством другого списка, который GHC может распознать как транзитивный? Я не уверен. Предположим, у нас было что-то вроде

      class Subset' a b
transitive :: (Subset' a b, Subset' b c) => SomeProof a b -> SomeProof b c -> Dict (Subset' a c)

Я был бы удивлен, если бы можно было определить transitiveбез использования его доказательных аргументов. Кроме того, на самом деле использовать такое, вероятно, будет сложно или даже невозможно.

Subset'ограничения, вероятно, будут приблизительно выглядеть как одно из следующего:

      type Subset' a b = Union a b ~ Nub (Sort b)
type Subset' a b = Intersection a b ~ Nub (Sort a)

где вы можете или не можете использовать предоставленные определения Union, Sort, а также Nub, и вам придется придумать свой собственный Intersection. Я нисколько не сомневаюсь, что любой такой проект будет сложным. Вам придется использовать структуру предоставленных вам доказательств, чтобы построить необходимое равенство. А потом после всего этого... куда ты на самом деле попал? Это похоже на тупик.