Могу ли я ограничить тип семьи?
В моем недавнем ответе я случайно открыл этот старый каштан (такая старая программа, половина которой была написана Лейбницем в семнадцатом веке и написана моим папой на компьютере в семидесятых годах). Я оставлю современное немного, чтобы сэкономить пространство.
class Differentiable f where
type D f :: * -> *
newtype K a x = K a
newtype I x = I x
data (f :+: g) x = L (f x)
| R (g x)
data (f :*: g) x = f x :&: g x
instance Differentiable (K a) where
type D (K a) = K Void
instance Differentiable I where
type D I = K ()
instance (Differentiable f, Differentiable g) => Differentiable (f :+: g) where
type D (f :+: g) = D f :+: D g
instance (Differentiable f, Differentiable g) => Differentiable (f :*: g) where
type D (f :*: g) = (D f :*: g) :+: (f :*: D g)
Теперь вот расстраивающая вещь. Я не знаю, как оговорить это D f сам должен быть дифференцируемым. Конечно, эти экземпляры уважают это свойство, и, возможно, вы можете написать забавные программы, в которых будет использоваться возможность дифференцировать функтор, пробивать дыры во все большем количестве мест: расширения Тейлора и тому подобное.
Я хотел бы иметь возможность сказать что-то вроде
class Differentiable f where
type D f
instance Differentiable (D f)
и требуют проверки, что объявления экземпляра имеют type определения, для которых существуют необходимые экземпляры.
Может быть, более мирские вещи, как
class SortContainer c where
type WhatsIn c
instance Ord (WhatsIn c)
...
также было бы хорошо. Это, конечно, имеет обходной путь fundep
class Ord w => SortContainer c w | c -> w where ...
но попробовать тот же трюк для Differentiable кажется... хорошо... нерешительным.
Итак, есть ли хороший обходной путь, который дает мне повторяемость дифференцируемости? (Я думаю, я мог бы создать представление GADT и и и и... но есть ли способ, который работает с классами?)
И есть ли какие-то очевидные препятствия с предположением, что мы должны иметь возможность требовать ограничений на семейства типов (и, я полагаю, данных), когда мы их объявляем, а затем проверить, что экземпляры удовлетворяют им?
4 ответа
Конечно, очевидной вещью будет просто написать желаемое ограничение напрямую:
class (Differentiable (D f)) => Differentiable (f :: * -> *) where
Увы, GHC раздражается из-за этого и отказывается подыгрывать:
ConstrainTF.hs:17:1:
Cycle in class declaration (via superclasses):
Differentiable -> Differentiable
In the class declaration for `Differentiable'
Таким образом, как это часто бывает, когда мы пытаемся описать достаточно типичные ограничения типов, чтобы оставить GHC непокорным, мы должны прибегнуть к какой-то манере закулисного обмана.
Вспоминая некоторые важные особенности GHC, в которых участвует хакерство типов:
- Это параноидально из-за того, что недопущение на уровне типа далеко не пропорционально фактическим неудобствам, которые это влечет за собой для пользователя.
- Он с радостью примет решение о классах и экземплярах до того, как рассмотрит всю имеющуюся информацию.
- Он покорно попытается проверить все, что вы обманули.
Это ложные принципы, лежащие в основе знакомых старых ложных обобщенных примеров, когда типы объединяются после (~) чтобы улучшить поведение вывода типа хакерских конструкций определенного типа.
В этом случае, однако, вместо того, чтобы скрывать информацию о типах за GHC, нам нужно было бы каким-то образом не допустить, чтобы GHC заметил ограничение класса, которое является совершенно другим типом... хей-у-у, waaaitaminute....
import GHC.Prim
type family DiffConstraint (f :: * -> *) :: Constraint
type instance DiffConstraint f = Differentiable f
class (DiffConstraint (D f)) => Differentiable (f :: * -> *) where
type D f :: * -> *
Подъем своей петардой!
Это тоже реальная сделка. Они приняты, как вы надеетесь:
instance Differentiable (K a) where
type D (K a) = K Void
instance Differentiable I where
type D I = K ()
Но если мы предложим вместо этого какую-то ерунду:
instance Differentiable I where
type D I = []
GHC представляет нам именно то сообщение об ошибке, которое мы хотели бы видеть:
ConstrainTF.hs:29:10:
No instance for (Differentiable [])
arising from the superclasses of an instance declaration
Possible fix: add an instance declaration for (Differentiable [])
In the instance declaration for `Differentiable I'
Конечно, есть одна маленькая загвоздка, а именно:
instance (Differentiable f, Differentiable g) => Differentiable (f :+: g) where
type D (f :+: g) = D f :+: D g
... оказывается менее чем обоснованным, как мы сказали GHC проверять это всякий раз, когда (f :+: g) является Differentiableтак это (D f :+: D g), который не заканчивается хорошо (или вообще).
Самый простой способ избежать этого, как правило, состоит в том, чтобы объединить в кучу явные базовые случаи, но здесь GHC, похоже, намеревается расходиться в любое время. Differentiable ограничение появляется в контексте экземпляра. Я бы предположил, что он как-то излишне рвется проверять ограничения экземпляров, и, возможно, его можно отвлекать достаточно долго с помощью другого уровня обмана, но я не сразу уверен, с чего начать, и исчерпал свои возможности для хакерских атак после полуночи сегодня вечером.
Немного IRC-дискуссии на #haskell удалось немного потрясти мою память о том, как GHC обрабатывает ограничения контекста класса, и кажется, что мы можем немного исправить ситуацию с помощью семейства ограничений выбора. Используя это:
type family DiffConstraint (f :: * -> *) :: Constraint
type instance DiffConstraint (K a) = Differentiable (K a)
type instance DiffConstraint I = Differentiable I
type instance DiffConstraint (f :+: g) = (Differentiable f, Differentiable g)
Теперь у нас гораздо более корректная рекурсия для сумм:
instance (Differentiable (D f), Differentiable (D g)) => Differentiable (f :+: g) where
type D (f :+: g) = D f :+: D g
Однако рекурсивный случай не может быть так просто разделен на две части для продуктов, и применение тех же изменений там улучшило дело только в том случае, если я получил переполнение стека сокращения контекста, а не просто зависание в бесконечном цикле.
Лучше всего определить что-то, используя constraints пакет:
import Data.Constraint
class Differentiable (f :: * -> *) where
type D f :: * -> *
witness :: p f -> Dict (Differentiable (D f))
тогда вы можете вручную открыть словарь всякий раз, когда вам понадобится повторение.
Это позволило бы вам использовать общую форму решения в ответе Кейси, но не заставило бы компилятор (или среду выполнения) вращаться вечно по индукции.
С новым UndecidableSuperclasses в GHC 8
class Differentiable (D f) => Differentiable (f :: Type -> Type) where
работает.
Это может быть выполнено так же, как предлагает Эдвард, с крошечной реализацией Dict, Во-первых, давайте уберем языковые расширения и импорт.
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE RankNTypes #-}
import Data.Proxy
TypeOperators только для вашего примера проблемы.
Крошечный Дикт
Мы можем сделать нашу собственную крошечную реализацию Dict, Dict использует GADT и ConstraintKinds захватить любое ограничение в конструкторе для GADT.
data Dict c where
Dict :: c => Dict c
withDict а также withDict2 повторно ввести ограничение путем сопоставления с образцом в GADT. Нам нужно только уметь рассуждать о терминах с одним или двумя источниками ограничений.
withDict :: Dict c -> (c => x) -> x
withDict Dict x = x
withDict2 :: Dict a -> Dict b -> ((a, b) => x) -> x
withDict2 Dict Dict x = x
Бесконечно дифференцируемые типы
Теперь можно говорить о бесконечно дифференцируемых типах, производные которых также должны быть дифференцируемыми.
class Differentiable f where
type D f :: * -> *
d2 :: p f -> Dict (Differentiable (D f))
-- This is just something to recover from the dictionary
make :: a -> f a
d2 берет прокси для типа и восстанавливает словарь для получения второй производной. Прокси позволяет нам легко указать, какой тип d2 мы говорим о. Мы можем добраться до более глубоких словарей, применяя d:
d :: Dict (Differentiable t) -> Dict (Differentiable (D t))
d d1 = withDict d1 (d2 (pt (d1)))
where
pt :: Dict (Differentiable t) -> Proxy t
pt = const Proxy
Захват диктонары
Полиномиальные типы функторов, произведения, суммы, константы и ноль являются бесконечно дифференцируемыми. Мы определим d2 свидетели для каждого из этих типов
data K x = K deriving (Show)
newtype I x = I x deriving (Show)
data (f :+: g) x = L (f x)
| R (g x)
deriving (Show)
data (f :*: g) x = f x :&: g x deriving (Show)
Ноль и константы не требуют никаких дополнительных знаний, чтобы захватить их производные Dict
instance Differentiable K where
type D K = K
make = const K
d2 = const Dict
instance Differentiable I where
type D I = K
make = I
d2 = const Dict
Sum и product требуют, чтобы словари из обоих производных их компонентов могли выводить словарь для их производных.
instance (Differentiable f, Differentiable g) => Differentiable (f :+: g) where
type D (f :+: g) = D f :+: D g
make = R . make
d2 p = withDict2 df dg $ Dict
where
df = d2 . pf $ p
dg = d2 . pg $ p
pf :: p (f :+: g) -> Proxy f
pf = const Proxy
pg :: p (f :+: g) -> Proxy g
pg = const Proxy
instance (Differentiable f, Differentiable g) => Differentiable (f :*: g) where
type D (f :*: g) = (D f :*: g) :+: (f :*: D g)
make x = make x :&: make x
d2 p = withDict2 df dg $ Dict
where
df = d2 . pf $ p
dg = d2 . pg $ p
pf :: p (f :*: g) -> Proxy f
pf = const Proxy
pg :: p (f :*: g) -> Proxy g
pg = const Proxy
Восстановление словаря
Мы можем восстановить словарь для ограничений, которые в противном случае у нас не было бы адекватной информации для вывода. Differentiable f обычно позволяет использовать только добраться до make :: a -> f a, но не для того или другого make :: a -> D f a или же make :: a -> D (D f) a,
make1 :: Differentiable f => p f -> a -> D f a
make1 p = withDict (d2 p) make
make2 :: Differentiable f => p f -> a -> D (D f) a
make2 p = withDict (d (d2 p)) make