Ограниченный гетерогенный список

Question

Я искал Hackage и не мог найти ничего подобного, но это кажется довольно простым и полезным. Есть ли библиотека, которая содержит тип данных?

data HList c where
  (:-) :: c a => a -> HList c
  Nil :: HList c

Все найденные мной списки HL могут иметь любой тип и не были ограничены.

Если нет, я загружу свой собственный.

Answer 1

Я не уверен, что этот тип данных полезен...

• Если вы действительно хотите a чтобы быть экзистенциально квалифицированным, я думаю, что вы должны использовать регулярные списки. Более интересный тип данных здесь будет Exists, хотя я уверен, что уже есть варианты всего пакета Hackage:

  data Exists c where
    Exists :: c a => a -> Exists c
  

  Тогда ваш HList c изоморфен [Exists c] и вы все еще можете использовать все обычные функции на основе списка.

• С другой стороны, если вы не обязательно хотите a в (:-) :: c a => a -> HList c быть экзистенциально квалифицированным (наличие такого рода не поддается HList), вместо этого вы должны определить следующее:

  data HList (as :: [*]) where
    (:-) :: a -> HList as -> HList (a ': as)
    Nil :: HList '[]
  

  Затем, если вы хотите, чтобы все записи HList удовлетворять c, вы можете сделать класс типа, чтобы засвидетельствовать инъекцию из HList as в [Exists c] чье разрешение экземпляра работает только если все типы в HList удовлетворить ограничение:

  class ForallC as c where
    asList :: HList as -> [Exists c]
  
  instance ForallC '[] c where
    asList Nil = []
  
  instance (c a, ForallC as c) => ForallC (a ': as) c where
    asList (x :- xs) = Exists x : asList xs
  

Answer 2

generics-sop Пакет предлагает это из коробки.

Разнородный список может быть определен в generics-sop используя

data NP :: (k -> *) -> [k] -> * where
  Nil  :: NP f '[]
  (:*) :: f x -> NP f xs -> NP f (x ': xs)

и создание его экземпляра для конструктора типа идентичности I (от generics-sop) или же Identity (от Data.Functor.Identity).

Затем библиотека предлагает ограничение All такой что например

All Show xs => NP I xs

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

type family All (f :: k -> Constraint) (xs :: [k]) :: Constraint where
  All c '[]       = ()
  All c (x ': xs) = (c x, All c xs)

(Только то, что в фактическом определении, All дополнительно упакован в класс типов, чтобы его можно было частично применить.)

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

Answer 3

То, что вы действительно хотите, это

data HKList :: (k -> *) -> [k] -> * where
  Nil  :: HKList f '[]
  (:*) :: f x -> HKList f xs -> HKList f (x ': xs)

Который вы можете использовать как обычный гетерогенный список

type HList = HKList Identity

Или с дополнительной информацией некоторого константного типа e прикрепленный к каждому значению (или другим интересным функторам)

HKList ((,) e)

Или с дополнительной информацией, записанной в словаре

data Has c a where
    Has :: c a => a -> Has c a

type ConstrainedList c = HKList (Has c)

Или сохранить списки только зафиксированных ограничений

data Dict1 :: (k -> Constraint) -> k -> * where
  Dict1 :: c k => Dict1 c k

Который вы можете использовать, чтобы определить идею всего списка типов, удовлетворяющих ограничению

class All c xs where
  dicts :: HKList (Dict1 c) xs

instance All c '[] where
  dicts = Nil

instance (All c xs, c x) => All c (x ': xs) where
  dicts = Dict1 :* dicts

Или все, что вы можете сделать с видом k -> *

Вы можете свободно конвертировать между работой с All c xs => HList xs а также HKList (Has c) xs

zipHKList :: (forall k. f k -> g k -> h k) -> HKList f xs -> HKList g xs -> HKList h xs
zipHKList _ Nil Nil = Nil
zipHKList f (x :* xs) (y :* ys) = f x y :* zipHKList f xs ys

allToHas :: All c xs => HKList Identity xs -> HKList (Has c) xs
allToHas xs = zipHKList f dicts xs
  where
    f :: Dict1 c k -> Identity k -> Has c k
    f Dict1 (Identity x) = Has x

hasToAll :: HKList (Has c) xs -> Dict (All c xs)
hasToAll Nil = Dict
hasToAll (Has x :* xs) =
  case hasToAll xs of
    Dict -> Dict

полный код

Я писал это несколько раз раньше для различных проектов, но я не знал, что это было в библиотеке, пока Космикус не указал, что это вgenerics-sop,