Изоморфизмы между 3 и более типами с использованием линзы

Вдохновленный вопросом о полиморфной функции между АТД, я пытаюсь создать изоморфизмы между несколькими (а не только двумя) типами, поэтому что каждый раз, когда мне нужен изоморфный, но не такой же тип, я могу посыпать свой код каким-нибудь convert.

Предположим, у меня есть 3 ADT:

data AB = A | B deriving (Show)
data CD = C | D deriving (Show)
data EF = E | F deriving (Show)

Используя lens, я могу реализовать 2 изоморфизма между AB и CD, CD и EF:

{-# LANGUAGE MultiParamTypeClasses #-}
class Isomorphic a b where
  convert :: Iso' a b

instance Isomorphic AB CD where
  convert = iso ab2cd cd2ab
    where ab2cd A = C
          ab2cd B = D
          cd2ab C = A
          cd2ab D = B

instance Isomorphic AB EF where
  convert = iso ab2ef ef2ab
    where ab2ef A = E
          ab2ef B = F
          ef2ab E = A
          ef2ab F = B

Преобразовать A в E легко: A^.convert :: EF. Преобразовать D в B также легко: D^.from convert :: AB. Но если я хочу преобразовать из C в E через A, я должен аннотировать типы для каждого промежуточного преобразования:

(C^.from convert :: AB)^.convert :: EF

Я понимаю, почему компилятор не может вывести промежуточные типы. Возможно, существует несколько изоморфизмов, посредством которых можно перейти от C к E. Но могу ли я упростить свой код, чтобы не аннотировать типы вручную везде?

Я мог бы просто написать еще один экземпляр для прямого преобразования между CD и EF, но что, если у меня больше трех типов? Если бы у меня было 5 изоморфных типов, мне пришлось бы указать 10 экземпляров, потому что количество изоморфных изображений между изоморфными объектами — это количество ребер в полном графе, который представляет собой треугольное число. Я бы предпочел указать n-1 экземпляров с компромиссом: я напишу больше convert или from convert.

Существует ли идиоматический способ установить изоморфизм между несколькими типами с помощью Iso< /a> из lens, чтобы было как можно меньше шаблонов и мне не нужно было все печатать и комментировать? Если мне нужно использовать для этого TemplateHaskell, как мне это сделать?

Мотивация в том, что в моей работе много до смешного сложных, но глупых типов, где () -> (() -> ()) -> X и ((), X) изоморфны X. Мне приходится вручную оборачивать и разворачивать все, и мне нужен полиморфный способ свести сложные типы к более простым изоморфным типам.


type-conversion haskell haskell-lens isomorphism
person Mirzhan Irkegulov    schedule 09.09.2016    source источник
comment
Жаль, что новый Data.Coerce не очень полезен для этого.   -  person jberryman    schedule 09.09.2016

Ответы (1)


arrow_upward
11
arrow_downward

Вы можете структурировать свои изоморфизмы в виде звездного графа: иметь канонический тип «хаба», к которому подключаются все остальные. Недостатком является то, что вам придется явно указывать концентратор в каждом экземпляре, и вы сможете конвертировать только между типами, которые совместно используют концентратор. Однако ваши два требования (хорошее определение типа и линейное количество экземпляров) будут выполнены. Вот как вы это сделаете:

{-# LANGUAGE TypeFamilies #-}
import Control.Lens
import Unsafe.Coerce

data AB = A | B deriving (Show)
data CD = C | D deriving (Show)
data EF = E | F deriving (Show)

class Isomorphic a where
    type Hub a
    convert :: Iso' a (Hub a)

viaHub :: (Isomorphic a, Isomorphic b, Hub a ~ Hub b) => a -> b
viaHub x = x ^. convert . from convert

instance Isomorphic AB where
    type Hub AB = AB
    convert = id

instance Isomorphic CD where
    type Hub CD = AB
    convert = unsafeCoerce -- because I'm too lazy to do it right

instance Isomorphic EF where
    type Hub EF = AB
    convert = unsafeCoerce

В ГКИ:

> viaHub A :: EF
E
> viaHub A :: CD
C
> viaHub E :: AB
A
> viaHub E :: CD
C

Вот как вы можете использовать это для своих примеров:

class Unit a where unit :: a
instance Unit () where unit = ()
instance Unit b => Unit (a -> b) where unit _ = unit

instance Isomorphic X where
    type Hub X = X
    convert = id

instance (Unit a, Isomorphic b) => Isomorphic (a -> b) where
    type Hub (a -> b) = Hub b
    convert = iso ($unit) const . convert

instance Isomorphic a => Isomorphic ((), a) where
    type Hub ((), a) = Hub a
    convert = iso snd ((,)()) . convert

instance Isomorphic a => Isomorphic (a, ()) where
    type Hub (a, ()) = Hub a
    convert = iso fst (flip(,)()) . convert

Теперь у вас будет, например.

viaHub :: (() -> (() -> ()) -> X) -> ((), X)
person Daniel Wagner    schedule 09.09.2016
comment
Большое спасибо, это здорово! Один вопрос: что, если я хочу обобщить конкретный тип X на любой тип, который можно рассматривать как канонический (т.е. (Int, String, Char) канонический, а (() -> ()) -> (Int, String, Char) нет)? Я работаю не только с X, но и с произвольными типами, включая произвольные кортежи. - person Mirzhan Irkegulov; 10.09.2016
comment
@MirzhanIrkegulov Спасибо, что обнаружили для меня мою ошибку. =) Вам понадобятся базовые случаи для всех типов, которые вы считаете каноническими. Я действительно не думаю, что есть способ обойти это, независимо от того, какой дизайн вы выберете. - person Daniel Wagner; 10.09.2016
comment
Проведя несколько часов, я все еще не понимаю, как интегрировать изоморфизм ((),()) ≅ () в приведенную выше схему. Я так или иначе сталкиваюсь с конфликтующими семейными случаями. - person Mirzhan Irkegulov; 10.09.2016
comment
@MirzhanIrkegulov Это немного прискорбно, да. Обратите внимание на разницу между случаем со стрелкой — когда мы можем позволить себе решить, что одна сторона стрелки определенно является единицей, которую мы планируем выбросить, поэтому мы можем быть полиморфными и придерживаться Unit a в контексте — и случаем кортежа -- где любая сторона может быть единицей, поэтому два определенных мною экземпляра должны быть мономорфными. Я точно не знаю, что с этим делать; лучшая вещь, которую я могу придумать, требует изрядного количества вычислений на уровне типов, которые будут тяжелым молотком для такого тонкого гвоздя. - person Daniel Wagner; 11.09.2016