Как создать экземпляр ListIsomorphic для универсальных векторов?

Question

Учитывая следующий класс:

class ListIsomorphic l where
    toList   :: l a -> [a]
    fromList :: [a] -> l a

Как я могу написать экземпляр для векторных типов, используя Data.Vector.Generic? Это не работает:

instance (V.Vector v a) => ListIsomorphic v where
    toList   = V.toList
    fromList = V.fromList

Давая мне:

test.hs:31:10:
    Variable ‘a’ occurs more often than in the instance head
      in the constraint: V.Vector v a
    (Use UndecidableInstances to permit this)
    In the instance declaration for ‘ListIsomorphic v’

Answer 1

Не Добавление экземпляра для всех v на ваш Listable Класс станет громоздким для использования из-за перекрывающихся экземпляров.

Vector v a => v не изоморфен списку, поскольку ограничен тем, какие элементы могут быть элементами списка. Вам нужен класс, который фиксирует это ограничение, что-то вроде

{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE TypeFamilies #-}

import Data.Constraint

class ConstrainedList l where
    type Elem l a :: Constraint
    toList   :: Elem l a => l a -> [a]
    fromList :: Elem l a => [a] -> l a

Вместо добавления ConstrainedList экземпляры для всех типов Vector v a => v что приведет нас к перекрывающейся территории экземпляров, вместо этого мы определим ее только для тех типов, которые нас интересуют. Далее будут рассмотрены все типы с Vector экземпляр в векторном пакете.

import qualified Data.Vector.Primitive as VP
import qualified Data.Vector.Generic as VG

instance ConstrainedList VP.Vector where
    type Elem VP.Vector a = VG.Vector VP.Vector a
    toList   = VG.toList
    fromList = VG.fromList

Экземпляры для других типов

Вы можете написать ConstrainedList экземпляр для обычных списков [] это требует только пустое ограничение для своих элементов.

instance ConstrainedList [] where
    type Elem [] a = ()
    toList   = id
    fromList = id

Везде, где используется toList или же fromList также потребует Elem l a пример.

cmap :: (ConstrainedList l, Elem l a, Elem l b) => (a -> b) -> l a -> l b
cmap f = fromList . map f . toList

Когда мы узнаем конкретные типы для списков и элементов, этими функциями будет легко пользоваться без возражений с ограничениями.

cmap (+1) [1,2,3,4]

Здесь быть драконами

Не пытайтесь, что следует. Если вас интересует класс вещей, изоморфных спискам без дополнительных ограничений, просто создайте для него другой класс. Это просто демонстрирует, что вы можете сделать, когда вы загнали себя в угол: вызвать дракона.

Вы также можете написать функции, которые требуют доказательства отсутствия ограничений на элементы ConstrainedList, Это далеко в царства constraints пакеты и стили программирования, которые на самом деле не поддерживаются GHC, но их недостаточно constraints примеры, поэтому я оставлю этот здесь.

{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE ScopedTypeVariables #-}

map' :: forall l a b. (ConstrainedList l, () :=> Elem l a, () :=> Elem l b) =>
                      (a -> b) -> l a -> l b
map' f = case (ins :: () :- Elem l a) of { Sub Dict ->
         case (ins :: () :- Elem l b) of { Sub Dict ->
         fromList . map f . toList
         }}

Мы могли бы проверить, что ConstrainedList не имеет ограничений, просто проверяя, что Elem l a ~ (), но это не сработало бы, если бы его ограничение было написано по-другому.

{-# LANGUAGE FlexibleInstances #-}

class Any a
instance Any a

data AList a = AList {getList :: [a]}
    deriving (Show)

instance ConstrainedList AList where
    type Elem AList a = Any a
    toList   = getList
    fromList = AList

() не тот же тип, что и Any a даже если () подразумевает Any a, Пакет ограничений фиксирует подобные отношения, преобразовывая их в классы типов. Class а также :=>

{-# LANGUAGE MultiParamTypeClasses #-}

--       class () => Any a
instance Class ()   (Any a) where
    cls = Sub Dict

-- instance ()  => Any a
instance    () :=> Any a where
    ins = Sub Dict

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

map'' :: (a -> b) -> AList a -> AList b
map'' = map'

Answer 2

Я часто сталкиваюсь с этой проблемой. Вот два решения, которые я придумала:

1. Измените параметры класса:

   class ListIsomorphic l a where
     toList :: l a -> [a]
     fromList :: [a] -> l a
   
   instance (V.Vector v a) => Listable v a where
     ...
   

2. Используйте виды ограничений

   class ListIsomorphic l where
     type C l a :: Constraint
     toList :: l a -> [a]
     fromList :: [a] -> l a
   
   instance Listable v where
     type C v a = (V.Vector v a)
     ...