Жонглирование существующими без unsafeCoerce - PullRequest
10 голосов
/ 30 июня 2019

В последнее время я играю с этим типом, который, как я понимаю, является кодировкой свободного дистрибутивного функтора (для тангенциального фона см. этот ответ ):

data Ev g a where
    Ev :: ((g x -> x) -> a) -> Ev g a

deriving instance Functor (Ev g)

Экзистенциальный конструктор гарантирует, что я могу потреблять только Ev g, поставляя полиморфный экстрактор forall x. g x -> x, и что функциям подъема и опускания свободной конструкции могут быть предоставлены совместимые типы:

runEv :: Ev g a -> (forall x. g x -> x) -> a
runEv (Ev s) f = s f

evert :: g a -> Ev g a
evert u = Ev $ \f -> f u

revert :: Distributive g => Ev g a -> g a
revert (Ev s) = s <$> distribute id

Однако при попытке дать Ev g экземпляр Distributive возникает трудность. Учитывая, что Ev g, в конечном счете, является просто функцией со странным типом аргумента, можно надеяться, что это просто потоковая distribute для функций (что составляет (??) :: Functor f => f (a -> b) -> a -> f b от lens , и никак не проверяет тип аргумента) через Ev обертку:

instance Distributive (Ev g) where
    distribute = Ev . distribute . fmap (\(Ev s) -> s)

Это, однако, не работает:

Flap3.hs:95:53: error:
    • Couldn't match type ‘x’ with ‘x0’
      ‘x’ is a rigid type variable bound by
        a pattern with constructor:
          Ev :: forall (g :: * -> *) x a. ((g x -> x) -> a) -> Ev g a,
        in a lambda abstraction
        at Flap3.hs:95:44-47
      Expected type: (g x0 -> x0) -> a
        Actual type: (g x -> x) -> a
    • In the expression: s
      In the first argument of ‘fmap’, namely ‘(\ (Ev s) -> s)’
      In the second argument of ‘(.)’, namely ‘fmap (\ (Ev s) -> s)’
    • Relevant bindings include
        s :: (g x -> x) -> a (bound at Flap3.hs:95:47)
   |
95 |     distribute = Ev . distribute . fmap (\(Ev s) -> s) 
   |                                                     ^
Failed, no modules loaded.

GHC возражает против переворачивания экзистенциала, хотя мы ничего не делаем с ним между развёртыванием и перепаковыванием. Единственный выход, который я нашел, - это прибегнуть к unsafeCoerce:

instance Distributive (Ev g) where
    distribute = Ev . distribute . fmap (\(Ev s) -> unsafeCoerce s)

Или, говоря это, возможно, более осторожно:

instance Distributive (Ev g) where
    distribute = eevee . distribute . fmap getEv
        where
        getEv :: Ev g a -> (g Any -> Any) -> a
        getEv (Ev s) = unsafeCoerce s
        eevee :: ((g Any -> Any) -> f a) -> Ev g (f a)
        eevee s = Ev (unsafeCoerce s)

Можно ли обойти эту проблему без unsafeCoerce? или действительно нет другого пути?

Дополнительные замечания:

  • Я считаю, Ev - самый правильный тип, который я могу придать конструкции, хотя я был бы рад оказаться ошибочным. Все мои попытки переместить квантификаторы в другое место привели либо к необходимости unsafeCoerce где-то еще, либо к evert и revert с типами, которые не позволяют их составлять.

  • Эта ситуация, на первый взгляд, похожа на ситуацию, описанную в этом сообщении в блоге Сэнди Магуайр , которое также заканчивается unsafeCoerce.


Следующая попытка создания экземпляра Ev g Representable может помочь устранить проблему. Как отмечает dfeuer , это не должно быть возможным; неудивительно, что мне пришлось снова использовать unsafeCoerce:

-- Cf. dfeuer's answer.
newtype Goop g = Goop { unGoop :: forall y. g y -> y }

instance Representable (Ev g) where
    type Rep (Ev g) = Goop g
    tabulate f = Ev $ \e -> f (Goop (goopify e))
        where
        goopify :: (g Any -> Any) -> g x -> x
        goopify = unsafeCoerce
    index (Ev s) = \(Goop e) -> s e

Хотя goopify, конечно, выглядит тревожно, я думаю, здесь есть причина, по которой это безопасно. Экзистенциальное кодирование означает, что любой e, который будет передан обернутой функции, обязательно будет полиморфным для экстрактора типа элемента, который специализируется на Any только потому, что я просил об этом. В таком случае forall x. g x -> x - разумный тип для e. Этот танец специализации на Any только для того, чтобы быстро отменить его с unsafeCoerce, необходим, потому что GHC заставляет меня избавиться от экзистенциального, сделав выбор. Вот что произойдет, если я пропущу unsafeCoerce в этом случае:

Flap4.hs:64:37: error:
    • Couldn't match type ‘y’ with ‘x0’
      ‘y’ is a rigid type variable bound by
        a type expected by the context:
          forall y. g y -> y
        at Flap4.hs:64:32-37
      Expected type: g y -> y
        Actual type: g x0 -> x0
    • In the first argument of ‘Goop’, namely ‘e’
      In the first argument of ‘f’, namely ‘(Goop e)’
      In the expression: f (Goop e)
    • Relevant bindings include
        e :: g x0 -> x0 (bound at Flap4.hs:64:24)
   |
64 |     tabulate f = Ev $ \e -> f (Goop e) 
   |                                     ^
Failed, no modules loaded.

Пролегомена, необходимая для запуска кода здесь:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TypeFamilies #-}

import Data.Distributive
import Data.Functor.Rep
import Unsafe.Coerce
import GHC.Exts (Any)

-- A tangible distributive, for the sake of testing.
data Duo a = Duo { fstDuo :: a, sndDuo :: a }
    deriving (Show, Eq, Ord, Functor)

instance Distributive Duo where
    distribute u = Duo (fstDuo <$> u) (sndDuo <$> u)

Ответы [ 2 ]

2 голосов
/ 01 июля 2019

Каждый Distributive функтор может быть сделан Representable, хотя мы не можем доказать это в Haskell (я думаю, это не конструктивно).Но один из подходов к решению вашей проблемы - просто переключить классы.

newtype Evv f a = Evv
  {unEvv :: forall g. Representable g
         => (forall x. f x -> g x) -> g a}

instance Functor (Evv g) where
  fmap f (Evv q) = Evv $ \g -> fmap f (q g)

evert :: g a -> Evv g a
evert ga = Evv $ \f -> f ga

revert :: Representable g => Evv g a -> g a
revert (Evv f) = f id

newtype Goop f = Goop
  {unGoop :: forall x. f x -> x}

instance Distributive (Evv g) where
  collect = collectRep

instance Representable (Evv g) where
  type Rep (Evv g) = Goop g
  tabulate f = Evv $ \g -> fmap (\rg -> f (Goop $ \fx -> index (g fx) rg)) $ tabulate id
  index (Evv g) (Goop z) = runIdentity $ g (Identity . z)

Я еще не пробовал это с Distributive напрямую (как предполагает HTNW), но я не удивлюсь, если бы это былопросто невозможно по какой-то причине.

Предупреждение: я не доказал, что это на самом деле бесплатно Representable!

1 голос
/ 07 июля 2019

Предложения от danidiaz и dfeuer привели меня к кодированию тидье, хотя unsafeCoerce все еще необходимо:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TypeFamilies #-}

import Unsafe.Coerce
import GHC.Exts (Any)
import Data.Distributive
import Data.Functor.Rep

-- Px here stands for "polymorphic extractor".
newtype Px g = Px { runPx :: forall x. g x -> x }

newtype Ev g a = Ev { getEv :: Px g -> a }
    deriving Functor

runEv :: Ev g a -> (forall x. g x -> x) -> a
runEv s e = s `getEv` Px e

evert :: g a -> Ev g a
evert u = Ev $ \e -> e `runPx` u

revert :: Distributive g => Ev g a -> g a
revert (Ev s) = (\e -> s (mkPx e)) <$> distribute id
    where
    mkPx :: (g Any -> Any) -> Px g
    mkPx e = Px (unsafeCoerce e) 

instance Distributive (Ev g) where
    distribute = Ev . distribute . fmap getEv

instance Representable (Ev g) where
    type Rep (Ev g) = Px g
    tabulate = Ev 
    index = getEv

Переменная x в моей первоначальной формулировке Ev была, всердце, будучи универсально выраженным;Я просто замаскировал его как экзистенциальное за функциональной стрелкой.Хотя это кодирование позволяет писать revert без unsafeCoerce, оно переносит нагрузку на реализации экземпляра.Непосредственное использование универсального количественного определения в этом случае, в конечном счете, лучше, поскольку оно сохраняет магию сосредоточенной в одном месте.

Уловка unsafeCoerce здесь, по сути, та же, что продемонстрирована с tabulate в вопросе: xв distribute id :: Distributive g => g (g x -> x) специализируется на Any, а затем специализация немедленно отменяется, под fmap, с unsafeCoerce.Я считаю, что уловка безопасна, так как я достаточно контролирую то, что подается на unsafeCoerce.

Что касается избавления от unsafeCoerce, я действительно не вижу пути.Отчасти проблема в том, что мне кажется, что мне понадобится какая-то форма непредсказуемых типов, поскольку трюк unsafeCoerce в конечном итоге сводится к превращению forall x. g (g x -> x) в g (forall x. g x -> x).Для сравнения я могу написать смутно аналогичный, хотя и гораздо более простой сценарий, используя подмножество функциональных возможностей непредсказуемых типов, которые подпадают под сферу расширения mooted ExplicitImpredicativeTypes (см. GHC ticket # 14859 и ссылки там для обсуждения):

{-# LANGUAGE ImpredicativeTypes #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE RankNTypes #-}

newtype Foo = Foo ([forall x. Num x => x] -> Int)

testFoo :: Applicative f => Foo -> f Int
testFoo (Foo f) = fmap @_ @[forall x. Num x => x] f 
    $ pure @_ @[forall x. Num x => x] [1,2,3]
GHCi> :set -XImpredicativeTypes 
GHCi> :set -XTypeApplications 
GHCi> testFoo @Maybe (Foo length)
Just 3

distribute id, однако, является более тернистым, чем [1,2,3]id :: g x -> g x переменная типа, которую я хотел бы сохранить количественно, появляется в двух местах, причем одно из них является вторым аргументом типа для distribute (функтор (->) (g x)).По крайней мере, для моего неподготовленного глаза это выглядит совершенно неразрешимым.

...