Как я могу восстановить совместное использование в GADT?

В "Безопасный общий доступ" в Haskell Энди Гилл показывает, как восстановить общий доступ, существовавший на уровне Haskell, в DSL. Его решение реализовано в пакете data-reify. Можно ли изменить этот подход для работы с GADT? Например, учитывая этот GADT:

data Ast e where
  IntLit :: Int -> Ast Int
  Add :: Ast Int -> Ast Int -> Ast Int
  BoolLit :: Bool -> Ast Bool
  IfThenElse :: Ast Bool -> Ast e -> Ast e -> Ast e

Я хотел бы восстановить совместное использование, изменив вышеуказанный AST на

type Name = Unique

data Ast2 e where
  IntLit2 :: Int -> Ast2 Int
  Add2 :: Ast2 Int -> Ast2 Int -> Ast2 Int
  BoolLit2 :: Bool -> Ast2 Bool
  IfThenElse2 :: Ast2 Bool -> Ast2 e -> Ast2 e -> Ast2 e
  Var :: Name -> Ast2 e

посредством функции

recoverSharing :: Ast -> (Map Name, Ast2 e1, Ast2 e2)

(Я не уверен в типе recoverSharing.)

Обратите внимание, что я не забочусь о введении новых привязок через конструкцию let, но только в восстановлении обмена, существовавшего на уровне Haskell. Вот почему я recoverSharing вернул a Map.

Если это невозможно сделать как многоразовый пакет, можно ли это сделать, по крайней мере, для конкретного GADT?

Ответ 1

Интересная головоломка! Оказывается, вы можете использовать data-reify с помощью GADT. Вам нужна оболочка, которая скрывает тип в экзистенциальном. Тип позже может быть получен путем сопоставления шаблонов в типе данных Type.

data Type a where
  Bool :: Type Bool
  Int :: Type Int

data WrappedAst s where
  Wrap :: Type e -> Ast2 e s -> WrappedAst s

instance MuRef (Ast e) where
  type DeRef (Ast e) = WrappedAst
  mapDeRef f e = Wrap (getType e) <$> mapDeRef' f e
    where
      mapDeRef' :: Applicative f => (forall b. (MuRef b, WrappedAst ~ DeRef b) => b -> f u) -> Ast e -> f (Ast2 e u)
      mapDeRef' f (IntLit i) = pure $ IntLit2 i
      mapDeRef' f (Add a b) = Add2 <$> (Var Int <$> f a) <*> (Var Int <$> f b)
      mapDeRef' f (BoolLit b) = pure $ BoolLit2 b
      mapDeRef' f (IfThenElse b t e) = IfThenElse2 <$> (Var Bool <$> f b) <*> (Var (getType t) <$> f t) <*> (Var (getType e) <$> f e)

getVar :: Map Name (WrappedAst Name) -> Type e -> Name -> Maybe (Ast2 e Name)
getVar m t n = case m ! n of Wrap t' e -> (\Refl -> e) <$> typeEq t t'

Здесь весь код: https://gist.github.com/3590197

Изменить: Мне нравится использование Typeable в другом ответе. Поэтому я также сделал версию своего кода с Typeable: https://gist.github.com/3593585. Код значительно короче. Type e -> заменяется на Typeable e =>, что также имеет недостаток: мы больше не знаем, что возможные типы ограничены Int и Bool, что означает, что в IfThenElse должно быть ограничение Typeable e.

Ответ 2

Я попытаюсь показать, что это можно сделать для определенных GADT, используя GADT в качестве примера.

Я буду использовать пакет Data.Reify. Это требует от меня определения новой структуры данных, в которой заменяющие позиции заменяются параметром.

data AstNode s where
  IntLitN :: Int -> AstNode s
  AddN :: s -> s -> AstNode s
  BoolLitN :: Bool -> AstNode s
  IfThenElseN :: TypeRep -> s -> s -> s -> AstNode s

Обратите внимание, что я удаляю много информации о типе, которая была доступна в исходном GADT. Для первых трех конструкторов ясно, что такое связанный тип (Int, Int и Bool). Для последнего я буду помнить тип, используя TypeRep (доступный в Data.Typeable). Экземпляр для MuRef, требуемый пакетом reify, показан ниже.

instance Typeable e => MuRef (Ast e) where
  type DeRef (Ast e)     = AstNode
  mapDeRef f (IntLit a)  = pure $ IntLitN a
  mapDeRef f (Add a b)   = AddN <$> f a <*> f b
  mapDeRef f (BoolLit a) = pure $ BoolLitN a
  mapDeRef f (IfThenElse a b c :: Ast e) = 
    IfThenElseN (typeOf (undefined::e)) <$> f a <*> f b <*> f c

Теперь мы можем использовать reifyGraph, чтобы восстановить общий доступ. Однако много информации о типе было потеряно. Попробуем восстановить его. Я слегка изменил ваше определение Ast2:

data Ast2 e where
  IntLit2 :: Int -> Ast2 Int
  Add2 :: Unique -> Unique -> Ast2 Int
  BoolLit2 :: Bool -> Ast2 Bool
  IfThenElse2 :: Unique -> Unique -> Unique -> Ast2 e

График из пакета reify выглядит следующим образом (где e = AstNode):

data Graph e = Graph [(Unique, e Unique)] Unique

Давайте создадим новую структуру данных графа, где мы можем отдельно хранить Ast2 Int и Ast2 Bool (таким образом, когда информация о типе была восстановлена):

data Graph2 = Graph2 [(Unique, Ast2 Int)] [(Unique, Ast2 Bool)] Unique 
            deriving Show

Теперь нам нужно найти функцию Graph AstNode (результат reifyGraph) до Graph2:

recoverTypes :: Graph AstNode -> Graph2
recoverTypes (Graph xs x) = Graph2 (catMaybes $ map (f toAst2Int) xs) 
                                   (catMaybes $ map (f toAst2Bool) xs) x where
  f g (u,an) = do a2 <- g an
                  return (u,a2)

  toAst2Int (IntLitN a) = Just $ IntLit2 a
  toAst2Int (AddN a b)  = Just $ Add2 a b
  toAst2Int (IfThenElseN t a b c) | t == typeOf (undefined :: Int) 
                        = Just $ IfThenElse2 a b c
  toAst2Int _           = Nothing

  toAst2Bool (BoolLitN a) = Just $ BoolLit2 a
  toAst2Bool (IfThenElseN t a b c) | t == typeOf (undefined :: Bool) 
                          = Just $ IfThenElse2 a b c
  toAst2Bool _            = Nothing

Давайте сделаем пример:

expr = Add (IntLit 42) expr  

test = do
  graph <- reifyGraph expr
  print graph
  print $ recoverTypes graph

Печать

let [(1,AddN 2 1),(2,IntLitN 42)] in 1
Graph2 [(1,Add2 2 1),(2,IntLit2 42)] [] 1

В первой строке показано, что reifyGraph правильно восстановил общий доступ. Во второй строке показано, что найдены только Ast2 Int типы (что также правильно).

Этот метод легко адаптируется для других конкретных GADT, но я не вижу, как это можно сделать полностью общим.

Полный код можно найти на http://pastebin.com/FwQNMDbs.