Можно ли фильтровать список уровней типов на основе доступности определенного класса?

Я могу отделить функции от нулевых значений с помощью семейства типов, например: 

type family Funs (ts :: [*]) :: [*]
  where
    Funs '[ ] = '[ ]
    Funs ((a -> b): ts) = (a -> b): Funs ts
    Funs (k: ts) = Funs ts

Я хотел бы разделить типы, удовлетворяющие ограничению, например Show. Попытка по аналогии: 

type family Showable (ts :: [*]) :: [*]
  where
    Showable '[ ] = '[ ]
    Showable ((Show a => a): ts) = a: Showable ts
    Showable (k: ts) = Showable ts

- приводит к ошибке: 

    • Illegal qualified type: Show a => a
    • In the equations for closed type family ‘Showable’
      In the type family declaration for ‘Showable’
   |
35 |     Showable ((Show a => a): ts) = a: Showable ts
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Что можно сделать? Я согласен с решением, которое использует шаблон Haskell, или скромную хакерскую работу любого рода.

1 3
haskell constraints type-families

1 ответ:

Я не верю, что это можно сделать легко (без TH) из-за допущения открытого мира: GHC в основном никогда не разрешит отрицательное ограничение класса, потому что где-то может быть больше экземпляров, которые делают его истинным (и не играют хорошо с отдельной стратегией компиляции, которую использует GHC/Haskell). Таким образом, обычно невозможно-из чистого "регулярного" кода Хаскелла-решить, есть ли у типа экземпляр класса, и поэтому включать его или нет список.

Если вы хотите немного разбить отдельную компиляцию, рассматривая только экземпляры, которые находятся в области, когда модуль, над которым вы работаете, скомпилирован (т. е. которые находятся в области в исходном файле этого модуля), вы можете использовать плагины Template Haskell или GHC typechecker, чтобы получить что-то очень похожее на это поведение. Я знаю пару реализаций, делающих что-то подобное на уровне значений, включая ifcxt и ограничения-emerge. Я считаю, что эти библиотеки, особенно ifcxt (с которым я немного больше знаком), довольно просты: вы можете использовать функцию TH reify, чтобы получить ClassI Info для конкретного класса типов и используйте его поле [InstanceDec], чтобы получить список всех экземпляров, находящихся в области видимости во время компиляции. Затем вы можете создать одну ветвь для каждого конкретного экземпляра типа, которая добавляет заголовок экземпляра в список, и следовать за ним с одной ветвью catch-all, которая не будет. Возможно, Вам также потребуется сделать это рекурсивно, чтобы разберитесь с экземплярами, которые сами имеют ограничения.

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

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

class IsShow (a :: Type) (b :: Bool) where
instance {-# OVERLAPPABLE #-} (b ~ 'False) => IsShow a b where

И у вас есть ваши TH генерировать экземпляры, такие как: 

instance IsShow Int 'True where

Это имеет то преимущество, что если другой модуль определяет важные типы / экземпляры, вы должны иметь возможность использовать (примерно) тот же самый TH для расширения экземпляров IsShow с помощью эти новые экземпляры и ваши семейства типов, использующие IsShow , должны быть в порядке. Пакет ifcxt, связанный выше, делает в основном то же самое, но вместо того, чтобы делать необходимые хитрости, чтобы получить информацию на уровне типа, он просто генерирует функции, чтобы получить ее на уровне значения.

Это решение использует класс с функциональными зависимостями вместо семейства типов, поскольку OverlappingInstances позволяет дать классовому решению "случай по умолчанию". Я не уверен, есть ли они вообще. разумный способ дать семейству типов open случай по умолчанию, поэтому вы не сможете получить эту "расширяемость" при использовании семейств типов везде (вместо экземпляров fundep'D).

Ричард Айзенберг говорит

При раздельной компиляции отсутствие упорядочивания и проверка перекрытия необходимы для надежности типа.

Поэтому я думаю, что это может быть невозможно. Есть также несколько интересных дискуссий вокруг типа семьи против фундепса здесь: https://typesandkinds.wordpress.com/2015/09/09/what-are-type-families/
4