Tuesday, August 12, 2008

Combinatory Birds as Types

This post is composed nearly entirely of the work of readers responding to my previous post that dealt with combinatory logic combinators. That post implemented the Smullyan combinatory birds as functions. This is the obvious approach, as birds and λ-terms have a very simple and straightforward (obviously bidirectional) mapping. A few readers improved and explained some of my combinators (S and W) by using the ((->) a) Monad, and I rolled those improvements into the original post, but these improvements are still in the combinators-as-functions domain.

Two readers, ryani and david, provided implementations for two combinators that I've had difficulty with. I've implemented the "void" combinator from the Unlambda programming language (or as Smullyan calls it, the "hopelessly egocentric" bird) using only the S and K combinators. Haskell is (thankfully) not so restricted, so ryani implemented that combinator as a type and then as a class. The thrust of ryani's void-as-type implementation is as follows:
> {-# LANGUAGE RankNTypes #-}
> newtype Void = V { runV :: forall a. a -> Void }
> v :: Void
> v = V (\x -> v)
Simple and sweet! And, the ranked type resolves the type-circularity ("void x is of type void"). So, for example:
> :t runV v 0
runV v 0 :: Void
> :t runV v "hello"
runV v "hello" :: Void
> :t runV (runV v 0) "hello"
runV (runV v 0) "hello" :: Void
... etc ...
In my implementation, I represented that the "void" combinator is "enough" K combinators (where "enough" was more K combinators than applications); ryani takes that exact approach using a class-based implementation:
> class Voidable r where vc :: r
> instance Voidable () where vc = ()
> instance Voidable r => Voidable (a -> r) where vc = k vc
(so void is represented as the Haskell type and datum () (pron: "unit")) e.g.:
> vc "hello" :: ()
()
> vc "hello" 123 :: ()
()
> vc "hello" 123 (Just k) :: ()
()
As ryani points out, the type-checker supplies the correct number of K combinators to match the number of function applications. Neat!

I had left a question on how to implement the U, or Turing, combinator, and david demonstrated an implementation where the class of all combinatory birds were a type (with two free implementations of good-ole factorial, to boot):
> data Bird a = B (Bird a -> Bird a) | Value a

> app :: Bird a -> Bird a -> Bird a
> app (B f) x = f x

> lift :: (a -> a) -> Bird a
> lift f = B (\(Value x) -> Value (f x))

> unlift :: Bird a -> (a -> a)
> unlift f = \x -> case (f `app` Value x) of Value y -> y

> -- Uxy = y(xxy)
> u = B (\x -> B (\y -> y `app` (x `app` x `app` y)))

> -- sage1 = UU [geophf mumbles: "Sweet!"]
> sage1 = u `app` u

> -- Yx = x(Yx)
> sage2 = B (\x -> x `app` (sage2 `app` x))

> fix f = unlift (sage1 `app` B (\g -> lift (f (unlift g))))
> fix2 f = unlift (sage2 `app` B (\g -> lift (f (unlift g))))

> facR :: (Integer -> Integer) -> Integer -> Integer
> facR f n = if n == 1 then 1 else n * f (n - 1)

> fac = fix facR
> fac2 = fix2 facR
I'm sure both ryani and david would claim that the M combinator (where m x = x x), so useful in Smullyan for implementing several birds (such as the "void" combinator), is not hard to do in Haskell given the above implementations. Do you see how to do it? Wanna race?

10 comments:

David said...

(Hmm. This may turn out to be a double-post, in which case apologies; but for the moment there's no sign of the comment that I thought I just left.)

First I want to make sure that credit goes to the right place. 'My' implementation really was little more than a rehash of a post here: http://www.haskell.org/pipermail/haskell/2007-April/019320.html; certainly that's where the good ideas came from.

(Actually, it does seem to be rather easy to implement M following this scheme.)

Second, I should thank you for the original post. I'd seen a few recommendations for To Mock a Mockingbird, but it was your blog that persuaded me to buy it; and I very much enjoyed the book.

Anonymous said...

welcome to the wow power leveling cheap Wow gold service site, buy cheap wow gold,wow gold,world of warcraft power leveling buy wow gold

Adi said...

Oes Tsetnoc Seo Contest one of the ways in which we can learn seo besides Upaya Mengembalikan Jati Diri Bangsa. By participating in the Oes Tsetnoc or Mengembalikan Jati Diri Bangsa we can improve our seo skills. To find more information about Oest Tsetnoc please visit my Oes Tsetnoc pages. And to find more information about Mengembalikan Jati Diri Bangsa please visit my Mengembalikan Jati Diri Bangsa page and other update like as Beratnya Mengembalikan Jati Diri Bangsa, Mengembalikan Jati Diri Bangsa di perpanjang and Jangan Berhenti Mengembalikan Jati Diri Bangsa. Thank you So much.

Oes Tsetnoc | Lanjutkan Mengembalikan Jati Diri Bangsa

Juliana Kho said...

Togel Toto Macau
daftar game casino rollete
Togel Toto Macau
Togel Toto Macau
Togel Toto Macau

deposit dadu poker
dadu poker
agen dadu poker
login dadu poker
cara menang main poker dadu online

Juliana Kho said...

http://www.idnliveoglok.net/idn-live-oglok/
http://www.idnliveoglok.net/idn-live-oglok-versi-mobile/
http://www.registercasinoidnlive.com/deposit-game-dadu-poker-online/
toto 4D
http://www.registercasinoidnlive.com/daftar-game-dingdong-12d-idn-live/
dadu putar
dadu poker
idn live

Jenny Wijaya said...

sabung ayam s128
login bluebet33
agen cbet indonesia
daftar scr888
osg 777

live chat joker123

Juliana Kho said...

idn poker play

Doyan

http://www.s1288.me/

admin said...

so hard to read for newbie.
make sure to visiting my blog too :)

click >> 199.188.201.30

AgenJudiBola said...

PROMO HADIAH indonalo SPESIAL UNTUK KALIAN PECINTA BOLA ONLINE. DISINI KAMI AKAN MEMBERIKAN HADIAH HIBURAN UNTUK KALIAN DALAM FITUR PERMAINAN TEBAK SCORE DI SETIAP MINGGUNYA.

MAINKAN DAN MENANGKAN HADIAH TOTAL 500,000.00 RUPIAH TANPA DI UNDI!

Hadiah dari tebak skor ini adalah total IDR 500rb di bagi rata ,Contoh :
- jika ada 1 pemenang hadiah IDR 500rb
- jika ada 5 pemenang hadiah masing - masing @IDR100.000
- Jika ada 10 pemenang hadiah masing - masing @IDR50.000

SYARAT DAN KETENTUAN : ( Promo Tebak Skor Indonalo )

KONTAK PERSON INDONALO

Telp/WA : +85515416144
Line : Cs_Indonalo
Livechat : indonalo

Kunjungi juga blog Prediksi Togel Terjitu dibawah ini

Prediksi TOgel Online

Jessica Huang said...

PERMAINAN ONLINE TERBESAR DI INDONESIA

Website paling ternama dan paling terpercaya di Asia ^^
Sistem pelayanan 24 Jam Non-Stop bersama dengan CS Berpengalaman respon tercepat :)
Memiliki 8 Jenis game yang sangat digemari oleh seluruh peminat poker / domino

- Adu Q
- Bandar Q
- Bandar Sakong
- Bandar Poker
- Poker
- Domino 99
- Capsa Susun
- BANDAR66 / ADU BALAK ( GAME TERBARU )

Permainan Judi online yang menggunakan uang asli dan mendapatkan uang asli ^^
* Minimal Deposit : 20.000
* Minimal Withdraw : 20.000
* Deposit dan Withdraw 24 jam Non stop ( Kecuali Bank offline / gangguan )
* Bonus REFFERAL 15 % Seumur hidup tanpa syarat
* Bonus ROLLINGAN 0.3 % Dibagikan 5 hari 1 kali
* Proses Deposit & Withdraw PALING CEPAT
* Sistem keamanan Terbaru & Terjamin
* Poker Online Terpercaya
* Live chat yang Responsive
* Support lebih banyak bank LOKAL


Contact Us

Website SahabatQQ
WA 1 : +85515769793
WA 2 : +855972076840
LINE : SAHABATQQ
FACEBOOK : SahabatQQ Reborn
TWITTER : SahabatQQ
YM : cs2_sahabatqq@yahoo.com
Kami Siap Melayani anda 24 jam Nonstop

Daftar SahabatQQ