[OT] To Mock A Mockingbird

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[OT] To Mock A Mockingbird

Patrick LeBoutillier
Hi all,

I've been reading the book "To Mock A Mockingbird" by Robert Smullyan
recently and I don't get the part about the birds at all. I think I
understand that a bird is a function, but what would it's type be in
Haskell?

It says that birds hear a call and answer by another call, so I
thought String -> String or something like that. But if you have a
mockingbird that can answer what a bird would answer to itself, that
means that it's input must contain the other bird... Do all the birds
have the same type?


Thanks,

Patrick



--
=====================
Patrick LeBoutillier
Rosem?re, Qu?bec, Canada
Reply | Threaded
Open this post in threaded view
|

[OT] To Mock A Mockingbird

Brent Yorgey-2
On Wed, Sep 08, 2010 at 07:57:14AM -0400, Patrick LeBoutillier wrote:

> Hi all,
>
> I've been reading the book "To Mock A Mockingbird" by Robert Smullyan
> recently and I don't get the part about the birds at all. I think I
> understand that a bird is a function, but what would it's type be in
> Haskell?
>
> It says that birds hear a call and answer by another call, so I
> thought String -> String or something like that. But if you have a
> mockingbird that can answer what a bird would answer to itself, that
> means that it's input must contain the other bird... Do all the birds
> have the same type?

No, each bird has its own type; each bird represents some particular
combinator (= polymorphic function).

-Brent
Reply | Threaded
Open this post in threaded view
|

[OT] To Mock A Mockingbird

Lyndon Maydwell
I've just read this.

Check out: http://dkeenan.com/Lambda/

Best analysis ever.

On Wed, Sep 8, 2010 at 8:08 PM, Brent Yorgey <[hidden email]> wrote:

> On Wed, Sep 08, 2010 at 07:57:14AM -0400, Patrick LeBoutillier wrote:
>> Hi all,
>>
>> I've been reading the book "To Mock A Mockingbird" by Robert Smullyan
>> recently and I don't get the part about the birds at all. I think I
>> understand that a bird is a function, but what would it's type be in
>> Haskell?
>>
>> It says that birds hear a call and answer by another call, so I
>> thought String -> String or something like that. But if you have a
>> mockingbird that can answer what a bird would answer to itself, that
>> means that it's input must contain the other bird... Do all the birds
>> have the same type?
>
> No, each bird has its own type; each bird represents some particular
> combinator (= polymorphic function).
>
> -Brent
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners
>
Reply | Threaded
Open this post in threaded view
|

[OT] To Mock A Mockingbird

Stephen Tetley-2
In reply to this post by Brent Yorgey-2
On 8 September 2010 13:08, Brent Yorgey <[hidden email]> wrote:

> No, each bird has its own type; each bird represents some particular
> combinator (= polymorphic function).

Also, bear in mind that some of the birds cannot be typed in Haskell.
Reply | Threaded
Open this post in threaded view
|

[OT] To Mock A Mockingbird

Michael Vanier-2
In reply to this post by Patrick LeBoutillier
  On 9/8/10 4:57 AM, Patrick LeBoutillier wrote:

> Hi all,
>
> I've been reading the book "To Mock A Mockingbird" by Robert Smullyan
> recently and I don't get the part about the birds at all. I think I
> understand that a bird is a function, but what would it's type be in
> Haskell?
>
> It says that birds hear a call and answer by another call, so I
> thought String ->  String or something like that. But if you have a
> mockingbird that can answer what a bird would answer to itself, that
> means that it's input must contain the other bird... Do all the birds
> have the same type?
>
>
> Thanks,
>
> Patrick
>
Patrick,

It's a cool book, well worth reading.  A bird is a function of a single
argument, which must be another bird, and it returns yet another bird.  
So the only kind of data are functions of a single argument which return
the same kinds of functions.  This is called "combinatory logic" (CL),
and is equivalent to what's called untyped lambda calculus (LC).  CL
terms can be converted to LC terms and vice-versa.  Haskell itself is
based on a system similar to LC (but much richer), and not all of the
terms in CL can be written in Haskell.  You can play with them in ghci:

ghci> let i x = x
ghci> :t i
i :: forall t: t -> t
ghci> let k x y = x
ghci> :t k
k :: forall t t1. t -> t1 -> t
ghci> let s x y z = (x z) (y z)
ghci> :t s
s :: forall t t1 t2. (t -> t1 -> t2) -> (t -> t1) -> t -> t2

s, k, and i are three basic combinators.  In fact, you can get i from s
and k:

ghci> let i2 = s k k
ghci> :t i2
i2 :: forall t. t -> t

i and i2 are the identity function (called "id" in Haskell).  k is
called "const" in Haskell.  s is a generalized function application
function.

However, some simple combinations of s, k, and i can't be typed in Haskell:

ghci> :t s i i
<interactive>:1:4:
     Occurs check: cannot construct the infinite type: t1 = t1 -> t2
     Probable cause: `i' is applied to too few arguments
     In the second argument of `s', namely `i'
     In the expression: s i i

That's because (s i i) is equivalent to this function:

ghci> let m z = z z

This is Smullyan's Mockingbird function.  Haskell doesn't allow
functions with so-called "infinite types" like this, even though they
can be useful (Haskell provides other ways to get what infinite types
would give you).

There is a long, fascinating road ahead of you if you decide to continue
studying this material :-)

Mike