Что такое поднятые и неподнятые типы продуктов в Haskell?

Недавно я столкнулся с термином «поднятый тип продукта», в отличие от неподнятого.

Я не могу вспомнить контекст, но я вижу, что в Stack Overflow есть другие вопросы о недостатках неподнятых типов продуктов (пример).

Я более или менее знаю, что такое тип продукта. Это что-то вроде (a, b) или Foo a b c, что примерно соответствует декартовому произведению из теории множеств.

Что означают термины «поднятый» и «неподнятый» в этом контексте?


types haskell
person jml    schedule 11.10.2016    source источник
comment
Связанный с этим вопрос: stackoverflow.com/ вопросы/27095011/   -  person danidiaz    schedule 11.10.2016

Ответы (2)


arrow_upward
11
arrow_downward

Из документов GHC :

«Поднятый» тип означает, что термины этого типа могут быть нижними.

«упакованный» тип означает, что значение представлено указателем на объект кучи.

Некоторые последствия включают:

Обратите внимание, что вы можете создавать неподнятые продукты в GHC, используя расширения MagicHash и UnboxedTuples (хотя я не думаю, что они хорошо работают с GHCi):

{-# LANGUAGE MagicHash, UnboxedTuples #-}

extGCD :: Int -> Int -> (# Int, Int, Int #)
extGCD a 0 = (# 1, 0, a #)
extGCD a b = let (q, r) = a `quotRem` b
                 (# s, t, g #) = extGCD b r
             in  (# t, s - q * t, abs g #)

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

Последнее замечание: в то время как расширенные типы имеют вид *, неподнятые типы имеют вид #. Этот ответ на вопрос, указанный в комментариях, содержит более подробную информацию об этом.

person Alec    schedule 11.10.2016
comment
Полиморфизм не работает с неподнятыми типами: bzzzt. Полиморфизм не работает с типами unboxed. Полиморфизм отлично работает с неподнятыми типами, например, в ML (хотя система видов Haskell может быть недостаточно гибкой для его поддержки). - person Jonathan Cast; 13.10.2016
comment
@jcast Верно, я имел в виду комментарий в контексте системы видов Haskell, где переменные типа имеют вид *, если не указано иное. Следующая ссылка фактически показывает, как это ограничение может быть снято с помощью более новых функций легкомысленного полиморфизма GHC 8.0. Это проясняет? - person Alec; 13.10.2016
comment
полиморфизм может играть с неподнятыми типами, если вы этого хотите, используя вид полиморфизма: forall (k :: RuntimeRep) (t :: TYPE k) :) - person Poscat; 25.02.2021

arrow_upward
8
arrow_downward

Из документации GHC:

Lifted

A type is lifted iff it has bottom as an element.

Значение расширенного типа может быть bottom. То есть это может быть undefined, или, возможно, вычисление, которое никогда не завершается, или такое, которое выдает исключение.

Между тем, неподнятые типы не имеют этих потенциально неприятных дополнительных значений. Это может быть полезно на чисто «семантическом» уровне (если вам не нужны эти дополнительные значения), а также может способствовать более эффективной реализации за счет сокращения дорогостоящих косвенных действий. Оптимизация GHC под названием преобразование worker-wrapper использует это (см. раздел 5.1 связанной статьи).

Поднятые и неподнятые типы имеют разные виды. Поднятые типы живут в *, неподнятые типы — в #.

В настоящее время GHC не позволяет вам легко определять свои собственные сложные неподнятые типы данных. Но есть предложения, позволяющие это сделать.

person danidiaz    schedule 11.10.2016