Почему не вводить синонимы разрешить рекурсию в Haskell?

Может кто-нибудь объяснить, почему они оба скомпилируются с радостью:

data A a b = A { a :: a, b :: b }
newtype B a = B (A a (B a))
newtype C = C (A Int C)

Но я не могу создать аналогично рекурсивно определенные типы через синонимы типов?

type B a = A a (B a)
type C = A Int C

Хотя очевидно, что data B a = A { a :: a, b :: B a } работает просто отлично.

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

Любые прагмы, которые я должен использовать для повышения производительности с помощью специализированного типа данных C? Просто специализируйтесь на материалах?

Какой-нибудь умный трюк для копирования между A a b и A c d, определяющий только сопоставление a -> b и c -> d без копирования за запись дважды? Боюсь, что поля A меняются в будущем. Возможно, шаблон Haskell?

Ответ 1

Это связано с Equi-recursive types против iso-recursive типы. Haskell реализует рекурсивные типы с использованием изорекурсивных типов, которые требуют от программиста рассказать контролеру типа, когда происходит рекурсия типа. То, как вы отмечаете это, связано с конкретным конструктором, который простой синоним типа не позволяет вам иметь.

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

Если вы хотите хорошо обсуждать equi vs. iso-рекурсивные типы, посмотрите Benjamin Pierce отлично Типы и языки программирования

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

Ответ 2

Я отвечу на ваш первый вопрос и на другие вопросы.

Тип B - бесконечный тип (A a (A a (A a (A a (...)))))

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

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

Нет. Haskell решил разрешить рекурсивные типы только с явными конструкторами типов от data или newtype. Это делает код более подробным, но newtype должен иметь небольшое время исполнения. Это дизайнерское решение.