[Haskell-cafe] type metaphysics

Joachim Breitner mail at joachim-breitner.de
Mon Feb 2 17:44:51 EST 2009


Hi,

Am Montag, den 02.02.2009, 14:41 -0800 schrieb Dan Piponi:
> 2009/2/2 Luke Palmer <lrpalmer at gmail.com>:
> 
> > But Nat ~> Bool is computably uncountable, meaning there is no injective (surjective?)
> > function Nat ~> (Nat ~> Bool), by the diagonal argument above.
> 
> Given that the Haskell functions Nat -> Bool are computably
> uncountable, you'd expect that for any Haskell function (Nat -> Bool)
> -> Nat there'd always be two elements that get mapped to the same
> value.
> 
> So here's a programming challenge: write a total function (expecting
> total arguments) toSame :: ((Nat -> Bool) -> Nat) -> (Nat -> Bool,Nat
> -> Bool) that finds a pair that get mapped to the same Nat.
> 
> Ie. f a==f b where (a,b) = toSame f
> --
> Dan
> 
> (PS I think this is hard. But my brain might be misfiring so it might
> be trivial.)

> toSame _ = (const True, const True)

;-)

Joachim

-- 
Joachim "nomeata" Breitner
  mail: mail at joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C
  JID: nomeata at joachim-breitner.de | http://www.joachim-breitner.de/
  Debian Developer: nomeata at debian.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: Dies ist ein digital signierter Nachrichtenteil
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20090202/96238046/attachment.bin


More information about the Haskell-Cafe mailing list