Замена одноэлементных типов данных семейством данных

Итак, в моем текущем проекте я выполняю кучу логики на уровне типов с одноэлементными типами.

Например:

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE GADTs #-}
module TypeBools where

type family (||) (a :: Bool) (b :: Bool) :: Bool where
  'False  || 'False = 'False
  'False  || 'True  = 'True
  'True   || 'False = 'True
  'True   || 'True  = 'True

data OrProof (a :: Bool) (b :: Bool) (c :: Bool) where
  OrProof :: SBool (a || b) -> OrProof a b (a || b)

data SBool (b :: Bool) where
  SFalse  :: SBool 'False
  STrue   :: SBool 'True

class Boolean b where
  sBool :: SBool b
instance Boolean 'False where
  sBool = SFalse
instance Boolean 'True where
  sBool = STrue

orProof :: (Boolean a, Boolean b) => OrProof a b (a || b)
orProof = go sBool sBool where

  go :: SBool a -> SBool b -> OrProof a b (a || b)
  go SFalse SFalse = OrProof SFalse
  go SFalse STrue = OrProof STrue
  go STrue SFalse = OrProof STrue
  go STrue STrue = OrProof STrue

И это работает очень хорошо для меня. Мне нравится не возиться с одноэлементными типами вручную, имея возможность вызывать их при необходимости через класс типов (например, класс Boolean выше), но это привело к множеству довольно похожих классов типов, которые существуют только для того, чтобы конкретизировать тип как одноэлементный. данные.

Я подумал, может быть, я мог бы абстрагировать эти несколько классов типов в одно семейство типов, например, заменив SBool и Boolean выше на:

{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE ConstraintKinds #-}
-- ...
class Singleton (t :: k) where
  data Sing t
  sing :: Sing t

instance Singleton 'False where
  data Sing 'False = SFalse
  sing = SFalse

instance Singleton 'True where
  data Sing 'True = STrue
  sing = STrue

type SBool b = Sing (b :: Bool)

type Boolean b = Singleton (b :: Bool)
sBool :: Boolean b => SBool b
sBool = sing

Но затем я получаю ошибки сопоставления с образцом:

TypeBools2.hs:42:13:
    Couldn't match type ‘b1’ with ‘'True’
      ‘b1’ is a rigid type variable bound by
           the type signature for
             go :: SBool a1 -> SBool b1 -> OrProof a1 b1 (a1 || b1)
           at TypeBools2.hs:40:9
    Expected type: SBool b1
      Actual type: Sing 'True
    Relevant bindings include
      go :: SBool a1 -> SBool b1 -> OrProof a1 b1 (a1 || b1)
        (bound at TypeBools2.hs:41:3)
    In the pattern: STrue
    In an equation for ‘go’: go SFalse STrue = OrProof STrue
    In an equation for ‘orProof’:
        orProof
          = go sBool sBool
          where
              go :: SBool a -> SBool b -> OrProof a b (a || b)
              go SFalse SFalse = OrProof SFalse
              go SFalse STrue = OrProof STrue
              go STrue SFalse = OrProof STrue
              go STrue STrue = OrProof STrue

Я не уверен, есть ли что-то еще, что я могу убедить компилятор в том, что b1 должен иметь тип Bool, или я просто лаю здесь не по тому дереву.


person rampion    schedule 21.04.2016    source источник
comment
Могу я спросить, почему ваш || не закорачивает? Например, я ожидаю лучшего сокращения с 'False || x = x; 'True || x = 'True.   -  person dfeuer    schedule 21.04.2016
comment
Вам следует просто использовать singletons, но если вы не собираетесь его использовать, вы должны увидеть, как они это делают, и скопировать (потому что они делают именно то, что вы хотите). В частности, вам нужно несвязанное семейство данных data family Sing (t :: k); class Singleton (t :: k) where sing :: Sing t и data instance Sing (b :: Bool) where ...   -  person user2407038    schedule 21.04.2016
comment
дфойер: может. Впрочем, это помимо вопроса.   -  person rampion    schedule 21.04.2016
comment
Кроме того, мне трудно понять, что должны выражать ваши OrProof и orProof. Они кажутся немного... окольными. Я знаю, что это не имеет прямого отношения к вашему вопросу.   -  person dfeuer    schedule 21.04.2016
comment
dfeuer: это упрощенный пример вопроса, но он позволяет вам выполнять логику на уровне типов, не беспокоясь о неспособности GHC (до 8) рассуждать об инъективности путем переноса аргументов. Например, or :: (Boolean a, Boolean b) => SBool (a || b); or = case orProof of OrProof c -> c дает старую ошибку неоднозначности NB: ‘||’ is a type function, and may not be injective.   -  person rampion    schedule 21.04.2016
comment
dfeuer: но мне еще нужен доступ к структуре финального типа, который я не могу получить от прокси.   -  person rampion    schedule 21.04.2016


Ответы (1)


Запрашиваемую функцию и многое другое можно найти в singletons. Это был окончательный шаблон для программирования на уровне типов в течение довольно долгого времени. Вы должны либо использовать его, либо скопировать реализацию. В любом случае, я сделаю здесь краткую демонстрацию упрощенного решения singletons.

Сопоставление с шаблоном не работает, потому что STrue и SFalse находятся в разных определениях данных, и это не GADT с самого начала. Сопоставление с образцом уточняет типы только в том случае, если оно выполняется на соответствующих GADT-ах. Нам нужно выполнить диспетчеризацию по видам, чтобы иметь возможность сгруппировать все одноэлементные конструкторы определенного вида.

Мы можем сделать это либо с помощью подходящего класса вида, либо с семейством данных верхнего уровня. Последнее проще для наших целей, так что давайте сделаем это:

data family Sing (x :: k)

data instance Sing (b :: Bool) where
  STrue :: Sing True
  SFalse :: Sing False

С sing нам не нужна добрая диспетчеризация, потому что мы используем ее только для получения определенных поднятых значений, поэтому работает следующее:

class SingI (x :: k) where
   sing :: Sing x

instance SingI True  where sing = STrue
instance SingI False where sing = SFalse

Что касается orProof, то мы хотели бы иметь синглтон для уровня типа (||), что проще всего достигается со следующим типом: Sing b1-> Sing b2 -> Sing (b1 || b2). Мы назовем его (%:||) в соответствии с иероглифической практикой именования singletons.

type family (:||) (b1 :: Bool) (b2 :: Bool) :: Bool where
  True  :|| b = True
  False :|| b = b

(%:||) :: Sing b1 -> Sing b2 -> Sing (b1 :|| b2)
(%:||) STrue  b2 = STrue
(%:||) SFalse b2 = b2

OrProof не очень полезен, так как это просто специализированный тип равенства вместе с ограничением SingI или простым Sing c:

type OrProof a b c = SingI c => c :~: (a :|| b)
type OrProof' a b c = (Sing c, c :~: (a :|| b))
person András Kovács    schedule 21.04.2016
comment
singletons в значительной степени есть все, что возможно с текущим GHC. Это не просто, поэтому не стесняйтесь задавать дополнительные вопросы, если у вас возникнут проблемы. На этом сайте у меня также есть несколько ответов, связанных с синглтонами, которые вы можете проверить. - person András Kovács; 21.04.2016