Понимание этого определения HList

Я относительно новичок в Haskell и пытаюсь понять одно из определений HList.

data instance HList '[] = HNil
newtype instance HList (x ': xs) = HCons1 (x, HList xs)
pattern HCons x xs = HCons1 (x, xs)

У меня есть пара конкретных вопросов:

  • Что такое синтаксис '[] и (x ': xs), который я вижу? Это почти похоже на сопоставление с образцом для параметров вариативного типа, но я никогда раньше не видел такого синтаксиса и не знаком с параметрами вариативного типа в Haskell. Я предполагаю, что это часть семейств типов GHC, но я ничего не вижу по этому поводу. на связанной странице, и довольно сложно искать синтаксис в Google.

  • Есть ли смысл использовать объявление newtype с кортежем (вместо объявления data с двумя полями), кроме как избегать упаковки HCons1?


person lcmylin    schedule 14.12.2016    source источник


Ответы (2)


Во-первых, вам не хватает части определения: самого объявления data family.

data family HList (l :: [*])
data instance HList '[] = HNil
newtype instance HList (x ': xs) = HCons1 (x, HList xs)

Это называется data family (доступно с расширением TypeFamilies).

pattern HCons x xs = HCons1 (x, xs)

Это двунаправленный шаблон (доступен с расширением PatternSynonyms).

Что такое синтаксис '[] и (x ': xs), который я вижу?

Знак ' перед конструкторами означает их продвигаемые аналоги на уровне типа. Для синтаксического удобства продвинутые списки и кортежи также нуждаются в дополнительной галочке (и мы по-прежнему можем писать '[] для пустого списка уровня типа и ': для минусов уровня типа. Все это доступно через расширение DataKinds.

Есть ли смысл использовать объявление newtype с кортежем (вместо объявления данных с двумя полями), кроме как избегать упаковки HCons1?

Да, чтобы убедиться, что HList имеет репрезентативную роль, что означает вы можете указать между HLists1. Это слишком сложно, чтобы объяснять просто ответом, но вот пример того, когда все идет не так, как мы хотим, когда у нас есть

 data instance HList (x ': xs) = HCons x (HList xs)

вместо newtype instance (и без шаблона). Рассмотрим следующие newtype, которые репрезентативно эквивалентны Int, Bool и () соответственно.

newtype MyInt = MyInt Int
newtype MyBool = MyBool Bool
newtype MyUnit = MyUnit ()

Напомним, мы можем использовать coerce для переноса или разворачивать эти типы автоматически. Ну, мы хотели бы иметь возможность делать то же самое, но в целом HList:

ghci> l  = (HCons 3 (HCons True (HCons () HNil))) :: HList '[Int,   Bool,   ()]
ghci> l' = coerce l                               :: HList '[MyInt, MyBool, MyUnit]

Это работает с вариантом newtype instance, но не с data instance из-за ролей. (Подробнее об этом здесь.)


1 технически, для data family в целом нет роли: роли могут быть разными для каждого instance/newtype - здесь нам действительно нужен только случай HCons, чтобы он был репрезентативным, так как именно он получает по принуждению. Проверьте этот билет Trac.

person Alec    schedule 14.12.2016
comment
Означает ли (l :: [*]) параметр типа l, ограниченный типом [*]? - person lcmylin; 14.12.2016
comment
@Textfield Точно! Параметр типа, который имеет расширенный список типов. Если подумать, для компиляции может потребоваться также включить KindSignatures и, возможно, импортировать Data.Kind... Просто делайте все, что вам советует GHC. :) - person Alec; 14.12.2016

'[] и (x ': xs) являются синтаксисом списков на уровне типов в том смысле, что DataKinds языковое расширение позволяет продвигать типы в виды и конструкторы в типы; т. е. если k какой-то вид, то '[k] тоже вид, а '[] тип вида '[k], а если t :: k и ts :: '[k], то t ': ts :: '[k]. Все смещается на один.

Таким образом, в HList (x ': xs), x и xs соответствуют два типа: x соответствует "нормальному" типу вида * (например, Int), а xs соответствует другому списку уровня типа вида '[*]. В правой части определяется тип данных (newtype), который имеет конструктор HCons1 с параметром типа (x, HList xs).

В качестве примера мы можем иметь

HCons1 (1, HCons1 (True, HNil)) :: HList '[Int, Bool]

Или, используя синоним шаблона:

1 `HCons` True `HCons` HNil :: HList '[Int, Bool]

У меня нет хорошего ответа на ваш второй вопрос о том, почему он представлен как новый тип с кортежем.

person Cactus    schedule 14.12.2016