Какво представляват типовете повдигнати и неповдигнати продукти в 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 документите:

„повдигнат“ тип означава, че термини от този тип може да са най-ниски.

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

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

  • Повдигнатият тип е в кутия (но не непременно по друг начин - вижте връзката по-горе за повече)
  • Типовете без кутия не могат да имат thunks (тъй като те са указатели към данни, които ви казват как да създадете стойността), така че без мързел. Те наистина държат само ценности. Това също означава, че те могат да бъдат по-бързи.
  • Полиморфизмът не играе с неповдигнати типове. Всеки път, когато видите променлива тип, всички включени типове не се повдигат. Нещо като id 0 :: Int# не работи. Вижте този отговор, за да видите как можете (от GHC 8.0 насам) понякога да маневрирате около това.

Имайте предвид, че можете да създавате продукти без повдигане в 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.

Стойност от повдигнат тип може да бъде отдолу. Тоест, може да бъде undefined или може би изчисление, което никога не завършва, или такова, което хвърля изключение.

Междувременно неповдигнатите типове нямат тези потенциално обезпокоителни допълнителни стойности. Това може да бъде полезно на чисто "семантично" ниво (ако не искате тези допълнителни стойности) и може също така да улесни по-ефективните имплементации чрез намаляване на скъпоструващите индиректи. Оптимизацията на GHC, наречена трансформация worker-wrapper използва това (вижте раздела 5.1 от свързания документ).

Повдигнатите и неповдигнатите типове имат различни видове. Повдигнатите типове живеят в *, неповдигнатите типове в #.

Понастоящем GHC не ви позволява лесно да дефинирате свои собствени сложни типове данни без повдигане. Но има предложения за това.

person danidiaz    schedule 11.10.2016