2013-01-03 6 views
81

absurd функция Data.Void имеет следующую подпись, где Void является логически необитаемым типом экспортируемого этого пакетом:Какая абсурдная функция в Data.Void полезна?

-- | Since 'Void' values logically don't exist, this witnesses the logical 
-- reasoning tool of \"ex falso quodlibet\". 
absurd :: Void -> a 

Я знаю достаточно логики, чтобы получить замечание в отношении документации, что это соответствует, по пропозициям, как -types, к действующей формуле ⊥ → a.

О чем я озадачен и интересуюсь: в чем проблема практического программирования, эта функция полезна? Я думаю, что, возможно, это полезно в некоторых случаях, поскольку безопасный способ исчерпывающего управления случаями «не может быть», но я не знаю достаточно о практических занятиях Карри-Ховарда, чтобы сказать, является ли эта идея на правый трек вообще.

EDIT: Примеры предпочтительно в Haskell, но если кто-то хочет использовать типизированный язык в зависимости я не собираюсь жаловаться ...

+5

Быстрый поиск показывает, что в этой статье использовалась функция 'absurd', посвященная монаде' Cont': http://www.haskellforall.com/2012/12/the-continuation-monad.html – Artyom

+6

Вы может видеть «абсурдным» как одно из направлений изоморфизма между «Пустотой» и «forall a». a'. –

ответ

49

Жизнь немного трудно, так как Haskell не является строги. Общий прецедент - обработка невозможных путей. Например,

simple :: Either Void a -> a 
simple (Left x) = absurd x 
simple (Right y) = y 

Это оказывается несколько полезным.Рассмотрим простой тип для Pipes

data Pipe a b r 
    = Pure r 
    | Await (a -> Pipe a b r) 
    | Yield !b (Pipe a b r) 

это строгая маньяков и упрощенный вариант стандартных труб типа из библиотеки Pipes Габриэля Гонсалеса. Теперь мы можем кодировать трубу, которая никогда не дает (то есть потребителя)

type Consumer a r = Pipe a Void r 

Это действительно никогда не дает. Следствием этого является то, что правильное правило раз для Consumer является

foldConsumer :: (r -> s) -> ((a -> s) -> s) -> Consumer a r -> s 
foldConsumer onPure onAwait p 
= case p of 
    Pure x -> onPure x 
    Await f -> onAwait $ \x -> foldConsumer onPure onAwait (f x) 
    Yield x _ -> absurd x 

или в качестве альтернативы, которые вы можете игнорировать случае выход при работе с потребителями. Это общая версия этого шаблона проектирования: используйте полиморфные типы данных и Void, чтобы избавиться от возможностей, когда вам нужно.

Возможно, наиболее классическое использование Void в CPS.

type Continuation a = a -> Void 

то есть Continuation это функция, которая никогда не возвращается. Continuation - это версия типа «нет». Отсюда мы получаем монаду КПС (соответствует классической логике)

newtype CPS a = Continuation (Continuation a) 

так Haskell чисто, мы не можем получить что-нибудь из этого типа.

+1

Да, я действительно могу любоваться этим битком CPS. Я, конечно же, слышал о двойном отрицании Карри-Говарда/соответствия CPS, но не понял его; Я не собираюсь требовать, чтобы я получил его сейчас, но это, безусловно, помогает! –

+0

_ «Жизнь немного сложна, так как Haskell не является строгой» - что вы имели в виду под этим? –

+1

@ErikAllik, на строгом языке, «Пустота» необитаема. В Haskell он содержит '_ | _'. Строго говоря, конструктор данных, который принимает аргумент типа «Void», никогда не может быть применен, поэтому правая часть совпадения шаблона недостижима. В Haskell вам нужно использовать '!' Для обеспечения этого, и GHC, вероятно, не заметит, что путь недоступен. – dfeuer

32

Я думаю, что, возможно, это полезно в некоторых случаях в качестве тип-безопасный способ исчерпывающей обработки «не может быть» случаи

Это точно.

Вы можете сказать, что absurd не более полезен, чем const (error "Impossible"). Однако он ограничен типом, поэтому его единственным входом может быть что-то типа Void, тип данных, который намеренно оставлен необитаемым. Это означает, что нет фактического значения, которое вы можете передать на absurd. Если вы когда-нибудь попадаете в ветку кода, где проверяющий тип думает, что у вас есть доступ к чему-то типа Void, то, ну, вы находитесь в ситуации absurd. Поэтому вы просто используете absurd, чтобы в основном отметить, что эта ветвь кода никогда не должна быть достигнута.

«Ex falso quodlibet» буквально означает «из [а] ложного [суждения], что-то следует». Поэтому, когда вы обнаружите, что у вас есть часть данных, тип которых Void, вы знаете, что у вас есть ложные доказательства в ваших руках. Поэтому вы можете заполнить любым отверстием, которое вы хотите (через absurd), потому что из ложного предложения все следует.

Я написал сообщение в блоге об идеях, стоящих за Conduit, в котором есть пример использования absurd.

http://unknownparallel.wordpress.com/2012/07/30/pipes-to-conduits-part-6-leftovers/#running-a-pipeline

12

Как правило, вы можете использовать его, чтобы избежать, по-видимому, частичный шаблон совпадает. Например, захватывая приближение деклараций типа данных из this answer:

data RuleSet a   = Known !a | Unknown String 
data GoRuleChoices  = Japanese | Chinese 
type LinesOfActionChoices = Void 
type GoRuleSet   = RuleSet GoRuleChoices 
type LinesOfActionRuleSet = RuleSet LinesOfActionChoices 

Тогда вы могли бы использовать absurd, как это, например:

handleLOARules :: (String -> a) -> LinesOfActionsRuleSet -> a 
handleLOARules f r = case r of 
    Known a -> absurd a 
    Unknown s -> f s 
57

Рассмотрите это представление для лямбда-терминов, параметризованных их свободными переменными. (См документы от Bellegarde и Hook 1994, Птица и Патерсон 1999, Altenkirch и Реус 1999.)

data Tm a = Var a 
      | Tm a :$ Tm a 
      | Lam (Tm (Maybe a)) 

Вы можете, конечно, сделать это Functor, захватив понятие переименования, и Monad захватывая понятие замещения.

instance Functor Tm where 
    fmap rho (Var a) = Var (rho a) 
    fmap rho (f :$ s) = fmap rho f :$ fmap rho s 
    fmap rho (Lam t) = Lam (fmap (fmap rho) t) 

instance Monad Tm where 
    return = Var 
    Var a  >>= sig = sig a 
    (f :$ s) >>= sig = (f >>= sig) :$ (s >>= sig) 
    Lam t  >>= sig = Lam (t >>= maybe (Var Nothing) (fmap Just . sig)) 

Теперь рассмотрим закрытые условия: это жители Tm Void. Вы должны иметь возможность встраивать замкнутые члены в члены с произвольными свободными переменными. Как?

fmap absurd :: Tm Void -> Tm a 

Улов, конечно, заключается в том, что эта функция будет пересекать термин, выполняющий точно ничто. Но это более честный контакт, чем unsafeCoerce. И поэтому vacuous был добавлен в Data.Void ...

Или напишите эксперта. Вот значения со свободными переменными в b.

data Val b 
    = b :$$ [Val b]        -- a stuck application 
    | forall a. LV (a -> Val b) (Tm (Maybe a)) -- we have an incomplete environment 

Я только что представил лямбды в качестве закрытий. Оценщик параметризуется переменными среды, отображающими свободные переменные в a, значениями до b.

eval :: (a -> Val b) -> Tm a -> Val b 
eval g (Var a) = g a 
eval g (f :$ s) = eval g f $$ eval g s where 
    (b :$$ vs) $$ v = b :$$ (vs ++ [v])   -- stuck application gets longer 
    LV g t  $$ v = eval (maybe v g) t  -- an applied lambda gets unstuck 
eval g (Lam t) = LV g t 

Вы угадали.Для того, чтобы оценить закрытый член в любой цели

eval absurd :: Tm Void -> Val b 

В целом, Void редко используется самостоятельно, но это удобно, когда вы хотите создать экземпляр параметра типа таким образом, что указывает на какой-то невозможности (например, здесь , используя свободную переменную в замкнутом члене). Часто эти параметризованные типы имеют функции подъема функций более высокого порядка по параметрам для операций по всему типу (например, здесь, fmap, >>=, eval). Таким образом, вы передаете absurd в качестве операции общего назначения на Void.

Для получения другого примера, предположите, используя Either e v для сбора вычислений, которые, надеюсь, дадут вам v, но могут возникнуть исключения типа e. Вы можете использовать этот подход для равномерного документирования риска плохого поведения. Для прекрасно вели себя вычислений в этой обстановке, принимать e быть Void, а затем использовать

either absurd id :: Either Void v -> v 

, чтобы безопасно работать или

either absurd Right :: Either Void v -> Either e v 

внедрить безопасные компоненты в небезопасном мире.

О, и последнее ура, обращение с «не может случиться». Он появляется в общей конструкции застежки-молнии, везде, где курсор не может быть.

class Differentiable f where 
    type D f :: * -> *    -- an f with a hole 
    plug :: (D f x, x) -> f x  -- plugging a child in the hole 

newtype K a  x = K a   -- no children, just a label 
newtype I  x = I x   -- one child 
data (f :+: g) x = L (f x)  -- choice 
        | R (g x) 
data (f :*: g) x = f x :&: g x -- pairing 

instance Differentiable (K a) where 
    type D (K a) = K Void   -- no children, so no way to make a hole 
    plug (K v, x) = absurd v  -- can't reinvent the label, so deny the hole! 

Я решил не удалять остальных, хотя это не совсем актуально.

instance Differentiable I where 
    type D I = K() 
    plug (K(), x) = I x 

instance (Differentiable f, Differentiable g) => Differentiable (f :+: g) where 
    type D (f :+: g) = D f :+: D g 
    plug (L df, x) = L (plug (df, x)) 
    plug (R dg, x) = R (plug (dg, x)) 

instance (Differentiable f, Differentiable g) => Differentiable (f :*: g) where 
    type D (f :*: g) = (D f :*: g) :+: (f :*: D g) 
    plug (L (df :&: g), x) = plug (df, x) :&: g 
    plug (R (f :&: dg), x) = f :&: plug (dg, x) 

На самом деле, может быть, это актуально. Если вы чувствуете приключений, это unfinished article показывает, как использовать Void сжать представление терминов со свободными переменными

data Term f x = Var x | Con (f (Term f x)) -- the Free monad, yet again 

в любом синтаксисе свободно генерируемой из Differentiable и Traversable функтора f. Мы используем Term f Void для представления областей без свободных переменных и [D f (Term f Void)] для представления трубок туннелирования по областям без свободных переменных либо к изолированной свободной переменной, либо к переходу на пути к двум или более свободным переменным. Должен закончить эту статью когда-нибудь.

Для типа без каких-либо значений (или, по крайней мере, ни один из них не стоит говорить в вежливой компании), Void замечательно полезен. И absurd - как вы его используете.

+0

Будет' forall f. vacuous f = unsafeCoerce f является допустимым правилом перезаписи GHC? – Cactus

+1

@Cactus, не совсем. Экземпляры Bogus 'Functor' могут быть GADT, которые на самом деле не похожи на функторов. – dfeuer

+0

Будут ли те 'Functor' нарушать правило 'fmap id = id'? Или это то, что вы подразумеваете под «фиктивным» здесь? – Cactus

10

Существуют различные способы представления the empty data type. Один из них - пустой алгебраический тип данных. Другой способ сделать это псевдоним для ∀α.α или

type Void' = forall a . a 

в Haskell - это то, как мы можем кодировать его в системе F (смотрите Главу 11 Proofs and Types). Эти два описания, конечно, изоморфны, и изоморфизм засвидетельствован \x -> x :: (forall a.a) -> Void и absurd :: Void -> a.

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

type Sink i m r = Pipe i i Void() m r 

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

absurd возникает, когда мы конвертируем между этими двумя представлениями.


Например, callcc :: ((a -> m b) -> m a) -> m a использует (неявное) forall b. Это может быть также тип ((a -> m Void) -> m a) -> m a, потому что вызов для продолжения фактически не возвращается, он передает управление другой точке. Если бы мы хотели работать с продолжениями, мы могли бы определить

type Continuation r a = a -> Cont r Void 

(Мы могли бы использовать type Continuation' r a = forall b . a -> Cont r b, но это было бы требовать ранга 2 типа.) А потом, vacuousM преобразует этот Cont r Void в Cont r b.

(Также обратите внимание, что вы можете использовать haskellers.com для поиска использования (обратной зависимость) определенного пакета, хотели бы видеть, кто и как использует поровые пакета .)

+0

['TypeApplications'] (https://downloads.haskell.org/~ghc/master/users-guide/glasgow_exts.html#ghc-flag--XTypeApplications) можно более подробно рассказать о деталях' proof: : (forall a.) -> Void': 'proof fls = fls @ Void'. –

0

В зависимом от типизированных языков, как Идрис , это, вероятно, более полезно, чем в Haskell. Как правило, в общей функции, когда шаблон совпадает с значением, которое на самом деле не может быть переброшено в функцию, вы затем должны построить значение нежилого типа и использовать absurd для завершения определения случая.

Например, эта функция удаляет элемент из списка с costraint типа уровня, что он присутствует там:

shrink : (xs : Vect (S n) a) -> Elem x xs -> Vect n a 
shrink (x :: ys) Here = ys 
shrink (y :: []) (There p) = absurd p 
shrink (y :: (x :: xs)) (There p) = y :: shrink (x :: xs) p 

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

С точки зрения Карри-Говарда, где есть предложения, то absurd является своего рода КЭД в доказательстве от противного.