Как Data.Void.absurd отличается от ⊥?

Я видел обратную абсурдную функцию ранее, и хотя мне ясно, что любая возможная реализация drusba :: a -> Void никогда не закончится (в конце концов, это невозможно для построения Void), я не понимаю, почему то же самое не относится к absurd :: Void -> a. Рассмотрим реализацию GHC:

newtype Void = Void Void

absurd :: Void -> a
absurd a = a `seq` spin a where
   spin (Void b) = spin b

spin, как мне кажется, бесконечно распутывает бесконечную серию оберток Void newtype и никогда не вернется, даже если вы можете найти Void для его передачи. Реализация, которая была бы неразличимой, была бы такой:

absurd :: Void -> a
absurd a = a `seq` undefined

Учитывая это, почему мы говорим, что absurd - это правильная функция, которая заслуживает того, чтобы жить в Data.Void, но

drusba :: a -> Void
drusba = undefined

- функция, которая не может быть определена? Это что-то вроде следующего?

absurd - это полная функция, дающая не-нижний результат для любого ввода в его (пустой) области, тогда как drusba является частичным, давая нижние результаты для некоторых (действительно всех) входов в его домене.

Ответы

Ответ 1

Data.Void переместился из пакета void в base в базовой версии 4.8 (GHC 7.10). Если вы посмотрите на файл Cabal для void, вы увидите, что он включает только Data.Void для старых версий base. Теперь void определяется как chi предлагает:

data Void

absurd :: Void -> a
absurd a = case a of {}

что вполне справедливо.

Я думаю, что идея старого определения выглядит примерно так:

Рассмотрим тип

data BadVoid = BadVoid BadVoid

Этот тип не выполняет задание, потому что на самом деле можно определить недвоенное (коиндуктивное) значение с этим типом:

badVoid = BadVoid badVoid

Мы можем исправить эту проблему, используя аннотацию строгости, которая (по крайней мере, вроде) заставляет тип быть индуктивным:

data Void = Void !Void

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

spin (Void x) = spin x

всегда заканчивается, если, предположительно, у нас есть что-то типа void.

Последний шаг заменяет тип данных single-strict-constructor новым типом:

newtype Void = Void Void

Это всегда законно. Однако определение spin изменило значение из-за различной семантики соответствия шаблонов между data и newtype. Чтобы точно сохранить значение, spin должно быть написано

spin !x = case x of Void x' -> spin x'

(избегая spin !(Void x), чтобы обрезать теперь исправленную ошибку во взаимодействии конструкторов newtype и шаблонов ударов, но для GHC 7.10 (ha!) эта форма фактически не выводит желаемое сообщение об ошибке, поскольку оно "оптимизировано" в бесконечный цикл), в котором точка absurd = spin.

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

Ответ 2

По историческим причинам любой тип данных Haskell (включая newtype) должен иметь хотя бы один конструктор.

Следовательно, для определения Void в "Haskell98" нужно полагаться на рекурсию уровня newtype Void = Void Void. Нет (без дна) значения этого типа.

Функция absurd должна опираться на рекурсию (уровень значения), чтобы справиться с "странной" формой типа Void.

В более современном Haskell с некоторыми расширениями GHC мы можем определить тип данных с нулевым конструктором, что приведет к более четкому определению.

{-# LANGUAGE EmptyDataDecls, EmptyCase #-}
data Void
absurd :: Void -> a
absurd x = case x of { }    -- empty case

Случай исчерпывающий - он обрабатывает все конструкторы Void, все они равны нулю. Следовательно, оно является полным.

В некоторых других функциональных языках, таких как Agda или Coq, вариант вышеприведенного случая является идиоматическим при работе с пустыми типами, такими как Void.