Mailing List Archive

tlug.jpMailing List tlug archive tlug Mailing List Archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]## [tlug] Re: Y Combinator

- Date: Mon, 09 Feb 2009 17:26:12 +0900
From:John Fremlin <john@example.com>Subject:[tlug] Re: Y Combinator- References: <20090129064805.GQ24024@smtp.office.cynic.net> <49867CF9.50006@bebear.net> <49893031.4000700@fremlin.org> <498BF621.1080608@bebear.net> <498C1622.70401@fremlin.org> <87k583eomm.fsf@xemacs.org>
- User-agent: Thunderbird 2.0.0.19 (X11/20090103)

Stephen J. Turnbull wrote:John Fremlin writes:

> > fix :: (a -> a) -> a > > fix f = let x = f x in x

> The main thing that puzzled me is that the type of fix is

> > fix :: (a -> a) -> a

> > but "a" must in fact have type

> b -> b

> because it's used as a function.

Is that a question, or does the past tense mean you got it?

Of course f is used as a function and thus must have a type of the form (a -> b), to have a fixed point it must be that a = b, and the fixed point itself must have the type a. Ergo

fix :: (a -> a) -> a

Yes, you are quite correct.

I was wrong to say that a must have type b->b in general. In fact there is no requirement for this. Thank you for explaining that.

I was confused, because I cannot see any reason for fix f, if f is of type a->a and the value returned by f depends only on its arguments, because either it must ignore its argument (and therefore be a constant) or fix f will not terminate.

To be concrete it is in fact possible to write this

Prelude> fix (\x -> 1) 1

Or even

Prelude> :t fix id fix id :: t Prelude> fix id ^CInterrupted.

In general, it is also possible to use multiple arguments, and they could even be of different types.

Prelude> fix (\x n -> if n == 0 then "zero" else "not zero") 0

"zero"

Prelude> :t fix (\x n -> if n == 0 then "zero" else "not zero")

fix (\x n -> if n == 0 then "zero" else "not zero") :: (Num a) => a -> [Char]

Prelude> fix(\x n y -> if n == 0 then y else n * y * (x (n-1) y)) 5 1 120

where

Prelude> :t fix(\x n y -> if n == 0 then y else n * y * (x (n-1) y))

fix(\x n y -> if n == 0 then y else n * y * (x (n-1) y)) :: (Num a) =>

a -> a -> a

Prelude> :t \x n y -> if n == 0 then y else n * y * (x (n-1) y)

\x n y -> if n == 0 then y else n * y * (x (n-1) y) :: (Num a) =>

(a -> a -> a) -> a -> a -> a

References:

Re: [tlug] Today's TSAC Meeting

From:Edward Middleton[tlug] Re: Today's TSAC Meeting

From:John Fremlin[tlug] Re: Y Combinator

From:Edward Middleton[tlug] Re: Y Combinator

From:John Fremlin[tlug] Re: Y Combinator

From:Stephen J. Turnbull

- Prev by Date:
Re: [tlug] EeePC so far- Next by Date:
Re: [tlug] EeePC so far- Previous by thread:
[tlug] Re: Y Combinator- Next by thread:
Re: [tlug] building ghc 6.10.1 under amd64 hardened Gentoo- Index(es):
Home | Main Index | Thread Index

Home Page Mailing List Linux and Japan TLUG Members Links