Apa fungsi absurd di Data.Void berguna untuk?

The absurdfungsi dalam Data.Voidmemiliki tanda tangan berikut, di mana Voidadalah jenis logis berpenghuni diekspor oleh paket yang:

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

Saya benar-benar tahu logika yang cukup untuk mendapatkan catatan dokumentasi bahwa ini sesuai, dengan korespondensi proposisi-sebagai-tipe, dengan rumus yang valid ⊥ → a.

Yang membuat saya bingung dan penasaran adalah: dalam masalah pemrograman praktis apa fungsi ini berguna? Saya berpikir bahwa mungkin ini berguna dalam beberapa kasus sebagai cara yang aman untuk menangani kasus "tidak dapat terjadi" secara menyeluruh, tetapi saya tidak cukup tahu tentang penggunaan praktis Curry-Howard untuk mengetahui apakah gagasan itu ada di jalur yang benar sama sekali.

EDIT: Contoh sebaiknya di Haskell, tetapi jika ada yang ingin menggunakan bahasa yang diketik secara dependen, saya tidak akan mengeluh ...

Hidup ini agak sulit, karena Haskell tidak ketat. Kasus penggunaan umum adalah untuk menangani jalur yang tidak mungkin. Sebagai contoh

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

Ini ternyata agak berguna. Pertimbangkan tipe sederhana untukPipes

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

ini adalah versi tipe pipa standar yang disederhanakan dan disederhanakan dari Pipesperpustakaan Gabriel Gonzales . Sekarang, kita dapat menyandikan pipa yang tidak pernah menghasilkan (yaitu, konsumen) sebagai

type Consumer a r = Pipe a Void r

ini benar-benar tidak pernah membuahkan hasil. Implikasinya adalah bahwa aturan lipatan yang tepat untuk a Consumeradalah

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

atau sebagai alternatif, Anda dapat mengabaikan kasus hasil saat berhadapan dengan konsumen. Ini adalah versi umum dari pola desain ini: gunakan tipe data polimorfik danVoid untuk menyingkirkan kemungkinan saat Anda membutuhkannya.

Mungkin penggunaan paling klasik Voidada di CPS.

type Continuation a = a -> Void

artinya, a Continuationadalah fungsi yang tidak pernah kembali. Continuationadalah jenis versi "tidak". Dari sini kita mendapatkan monad CPS (sesuai dengan logika klasik)

newtype CPS a = Continuation (Continuation a)

karena Haskell murni, kita tidak bisa mendapatkan apapun dari tipe ini.

Pertimbangkan representasi ini untuk istilah lambda yang diparameterisasi oleh variabel bebasnya. (Lihat makalah oleh Bellegarde dan Hook 1994, Bird dan Paterson 1999, Altenkirch dan Reus 1999.)

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

Anda pasti bisa membuat ini menjadi Functor, menangkap gagasan penggantian nama, dan Monadmenangkap gagasan substitusi.

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))

Sekarang pertimbangkan istilah tertutup : ini adalah penghuni Tm Void. Anda harus dapat menyematkan istilah tertutup ke dalam istilah dengan variabel bebas arbitrer. Bagaimana?

fmap absurd :: Tm Void -> Tm a

Tangkapannya, tentu saja, adalah bahwa fungsi ini akan melintasi istilah tanpa melakukan apa pun. Tapi itu sentuhan yang lebih jujur ​​daripada unsafeCoerce. Dan itulah mengapa vacuousditambahkan keData.Void ...

Atau tulis seorang evaluator. Berikut adalah nilai dengan variabel bebas di b.

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

Saya baru saja mewakili lambda sebagai penutup. Evaluator diparameterisasi oleh lingkungan yang memetakan variabel bebas ake nilai di atas 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

Anda dapat menebaknya. Untuk mengevaluasi istilah tertutup pada target apa pun

eval absurd :: Tm Void -> Val b

Lebih umum, Voidjarang digunakan sendiri, tetapi berguna ketika Anda ingin membuat contoh parameter tipe dengan cara yang menunjukkan semacam ketidakmungkinan (misalnya, di sini, menggunakan variabel bebas dalam istilah tertutup). Seringkali tipe parametrized ini hadir dengan operasi pengangkatan fungsi tingkat tinggi pada parameter ke operasi pada keseluruhan tipe (misalnya, di sini,fmap , >>=, eval). Jadi Anda lulus absurdsebagai operasi tujuan umum Void.

Untuk contoh lain, bayangkan menggunakan Either e vuntuk menangkap komputasi yang diharapkan memberi Anda vtetapi mungkin menimbulkan pengecualian jenise . Anda mungkin menggunakan pendekatan ini untuk mendokumentasikan risiko perilaku buruk secara seragam. Untuk sempurna berperilaku baik perhitungan dalam pengaturan ini, mengambil emenjadi Void, maka penggunaan

either absurd id :: Either Void v -> v

untuk berlari dengan aman atau

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

untuk menanamkan komponen yang aman di dunia yang tidak aman.

Oh, dan hore terakhir, menangani "tidak bisa terjadi". Ini muncul dalam konstruksi ritsleting umum, di mana pun kursor tidak bisa berada.

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!

Saya memutuskan untuk tidak menghapus sisanya, meskipun itu tidak terlalu relevan.

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)

Sebenarnya, mungkin itu relevan. Jika Anda suka berpetualang, artikel yang belum selesai ini menunjukkan cara menggunakan Voiduntuk mengompresi representasi istilah dengan variabel bebas

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

dalam sintaks yang dihasilkan secara bebas dari a Differentiabledan Traversablefunctor f. Kami menggunakan Term f Voiduntuk merepresentasikan kawasan tanpa variabel bebas, dan [D f (Term f Void)]untuk merepresentasikan saluran tabung melalui kawasan tanpa variabel bebas baik ke variabel bebas yang terisolasi, atau ke persimpangan di jalur ke dua atau lebih variabel bebas. Harus menyelesaikan artikel itu kapan-kapan.

Untuk tipe tanpa nilai (atau setidaknya, tidak ada yang layak dibicarakan dengan teman yang sopan), Voidsangat berguna. Dan absurdbagaimana Anda menggunakannya.

Saya berpikir bahwa mungkin ini berguna dalam beberapa kasus sebagai cara yang aman untuk menangani kasus "tidak dapat terjadi" secara menyeluruh

Ini memang benar.

Bisa dibilang itu absurdtidak lebih berguna dari const (error "Impossible"). Namun, ini adalah tipe yang dibatasi, sehingga input satu-satunya dapat berupa sesuatu yang bertipe Void, tipe data yang sengaja dibiarkan tak berpenghuni. Ini berarti tidak ada nilai aktual yang dapat Anda berikan absurd. Jika Anda pernah berakhir di cabang kode di mana pemeriksa tipe berpikir bahwa Anda memiliki akses ke sesuatu yang bertipe Void, maka, Anda berada dalam situasi yang tidak masuk akal . Jadi absurdpada dasarnya Anda hanya menggunakan untuk menandai bahwa cabang kode ini tidak boleh dijangkau.

"Ex falso quodlibet" secara harfiah berarti "dari [a] salah [proposisi], apapun mengikuti". Jadi, ketika Anda menemukan bahwa Anda memegang sepotong data yang tipenya adalah Void, Anda tahu Anda memiliki bukti palsu di tangan Anda. Oleh karena itu, Anda dapat mengisi lubang apa pun yang Anda inginkan (melaluiabsurd ), karena dari proposisi yang salah, apa pun mengikuti.

Saya menulis posting blog tentang ide di balik Conduit yang memiliki contoh penggunaan absurd.

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

Umumnya, Anda dapat menggunakannya untuk menghindari kecocokan pola yang tampaknya sebagian. Misalnya, mengambil perkiraan deklarasi tipe data dari jawaban ini :

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

Kemudian Anda bisa menggunakan absurdseperti ini, misalnya:

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

Ada berbagai cara untuk merepresentasikan tipe data kosong . Salah satunya adalah tipe data aljabar kosong. Cara lainnya adalah dengan membuatnya menjadi alias untuk ∀α.α atau

type Void' = forall a . a

di Haskell - ini adalah cara kita dapat menyandikannya di Sistem F (lihat Bab 11 tentang Bukti dan Jenis ). Kedua deskripsi ini tentu saja isomorfik dan isomorfisme disaksikan oleh \x -> x :: (forall a.a) -> Voiddan olehabsurd :: Void -> a .

Dalam beberapa kasus, kami lebih memilih varian eksplisit, biasanya jika tipe data kosong muncul dalam argumen suatu fungsi, atau dalam tipe data yang lebih kompleks, seperti di Data.Conduit :

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

Dalam beberapa kasus, kami lebih suka varian polimorfik, biasanya tipe data kosong terlibat dalam tipe kembalian suatu fungsi.

absurd muncul saat kita mengkonversi antara dua representasi ini.

Misalnya, callcc :: ((a -> m b) -> m a) -> m ause (implisit) forall b. Bisa juga jenisnya ((a -> m Void) -> m a) -> m a, karena panggilan ke kontinuitas tidak benar-benar kembali, ia mentransfer kontrol ke titik lain. Jika kami ingin bekerja dengan kelanjutan, kami dapat menentukan

type Continuation r a = a -> Cont r Void

(Kita bisa menggunakan type Continuation' r a = forall b . a -> Cont r btapi itu membutuhkan tipe peringkat 2.) Dan kemudian, vacuousMubah ini Cont r Voidmenjadi Cont r b.

(Perhatikan juga bahwa Anda dapat menggunakan haskellers.com untuk mencari penggunaan (ketergantungan terbalik) dari paket tertentu, seperti untuk melihat siapa dan bagaimana menggunakan paket void .)

Dalam bahasa dengan tipe dependen seperti Idris, ini mungkin lebih berguna daripada di Haskell. Biasanya, dalam fungsi total saat pola Anda cocok dengan nilai yang sebenarnya tidak dapat dimasukkan ke dalam fungsi, Anda kemudian akan membuat nilai dengan tipe tak berpenghuni dan digunakan absurduntuk menyelesaikan definisi kasus.

Misalnya, fungsi ini menghapus elemen dari daftar dengan tipe-cat costraint yang ada di sana:

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

Di mana kasus kedua mengatakan bahwa ada elemen tertentu dalam daftar kosong, yang sangat tidak masuk akal. Secara umum, bagaimanapun, kompilator tidak mengetahui hal ini dan kami sering harus eksplisit. Kemudian kompilator dapat memeriksa bahwa definisi fungsi tidak parsial dan kami memperoleh jaminan waktu kompilasi yang lebih kuat.

Melalui sudut pandang Curry-Howard, di mana proposisinya, maka absurdsemacam QED yang dibuktikan dengan kontradiksi.