Являются ли расширяемые GADT жизнеспособным решением проблемы выражения? - PullRequest
Новая
       97

Являются ли расширяемые GADT жизнеспособным решением проблемы выражения?

2 голосов
/ 16 марта 2020

Рассмотрим следующую желаемую программу. 

{-# LANGUAGE ExtensibleGADTs #-}

data Free a where
    Lift :: a -> Free a

data Free (f a) => FreeFunctor f a where
    Map :: (a -> b) -> FreeFunctor f a -> FreeFunctor f b

instance Functor (FreeFunctor f) where
    fmap = Map

data FreeFunctor f a => FreeApplicative f a where
    Apply :: FreeApplicative f (a -> b) -> FreeApplicative f a -> FreeApplicative f b
    Pure  :: a -> FreeApplicative f a

instance Applicative (FreeApplicative f) where
    (<*>) = Apply
    pure  = Pure

data FreeApplicative m a => FreeMonad m a where
    Bind :: FreeMonad m a -> (a -> FreeMonad m b) -> FreeMonad m b

instance Monad (FreeMonad m) where
    (>>=) = Bind

Это введет понятие заменяемость . Например, FreeApplicative f a может быть заменено FreeFunctor f a, но не FreeMonad f a. Точно так же FreeApplicative f a -> Int может быть заменен FreeMonad f a -> Int, но не FreeFunctor f a -> Int.

Понятие подтип может быть зафиксировано с помощью инъекций. 

import Unsafe.Coerce

fromFreeToFreeFunctor :: Free (f a) -> FreeFunctor f a
fromFreeToFreeFunctor = unsafeCoerce

fromFreeFunctorToFreeApplicative :: FreeFunctor f a -> FreeApplicative f a
fromFreeFunctorToFreeApplicative = unsafeCoerce

fromFreeApplicativeToFreeMonad :: FreeApplicative m a -> FreeMonad m a
fromFreeApplicativeToFreeMonad = unsafeCoerce

Компилятор вставляет эти инъекции по мере необходимости.

Я думаю, что это хорошее решение проблемы выражения . Тем не менее, общий консенсус заключается в том, что полиморфизм подтипа будет проблематичным c в Haskell. Итак, у меня вопрос в два раза.

  1. Подтипирование, как я описал выше, будет проблематичным c или помешает выводу типа в Haskell?
  2. Будет ли расширяемый GADT жизнеспособное решение проблемы выражения в Haskell?

Я еще не определил точную семантику для расширяемых GADT. Если это кажется чем-то стоящим, я хотел бы написать для этого расширение GH C. Просто хотел выпустить эту идею на волю и получить некоторую критику.

...