Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

492 views

Skip to first unread message

Sep 15, 2006, 8:11:48 AM9/15/06

to haskell

Hi,

Writing

yc = \f -> (\x -> f(x x)) (\x -> f(x x))

causes type error. Is there a way to define it in Haskell?

Thanks,

Haihua

_______________________________________________

Haskell mailing list

Has...@haskell.org

http://www.haskell.org/mailman/listinfo/haskell

Sep 15, 2006, 8:18:28 AM9/15/06

to Haihua Lin

Well, you can do it with the existing recursion in Haskell

let yc f = f (yc f)

Or you can encode it with type level recursion and no value recursion

by using a recursive data type.

let yc f = f (yc f)

Or you can encode it with type level recursion and no value recursion

by using a recursive data type.

-- Lennart

Sep 15, 2006, 12:46:12 PM9/15/06

to Haihua Lin

On 15/09/06, Haihua Lin <Haih...@163.com> wrote:

> Is there a way to define it in Haskell?

> Is there a way to define it in Haskell?

Note that the function 'fix' (find the fixpoint of a function) already

exists in Haskell, and is equivalent to the Y combinator.

It's interesting that most (all?) fixed-point combinators don't

typecheck. The Y combinator, and by extension recursion in general,

has to be added as a constant to the language.

--

-David House, dmh...@gmail.com

Sep 15, 2006, 1:47:29 PM9/15/06

to has...@haskell.org

On Friday 15 September 2006 12:45, David House wrote:

> On 15/09/06, Haihua Lin <Haih...@163.com> wrote:

> > Is there a way to define it in Haskell?

>

> Note that the function 'fix' (find the fixpoint of a function) already

> exists in Haskell, and is equivalent to the Y combinator.

>

> It's interesting that most (all?) fixed-point combinators don't

> typecheck. The Y combinator, and by extension recursion in general,

> has to be added as a constant to the language.

> On 15/09/06, Haihua Lin <Haih...@163.com> wrote:

> > Is there a way to define it in Haskell?

>

> Note that the function 'fix' (find the fixpoint of a function) already

> exists in Haskell, and is equivalent to the Y combinator.

>

> It's interesting that most (all?) fixed-point combinators don't

> typecheck. The Y combinator, and by extension recursion in general,

> has to be added as a constant to the language.

This actually isn't true. You can define a direct fixed point combinator

without relying on nominal recursion in Haskell, but it requires you to

define a helper newtype.

Don't run this in GHC because it will diverge. Hugs works, however.

newtype Mu a = Roll (Mu a -> (a -> a))

unroll (Roll x) = x

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

fix = \f -> (\x z -> f ((unroll x) x z))

(Roll (\x z -> f ((unroll x) x z)))

facF :: (Int -> Int) -> Int -> Int

facF f x

| x <= 0 = 1

| otherwise = x * (f (x-1))

fac :: Int -> Int

fac = fix facF undefined

main = print $ fac 5

Rob Dockins

Talk softly and drive a Sherman tank.

Laugh hard, it's a long way to the bank.

-- TMBG

Sep 15, 2006, 2:48:31 PM9/15/06

to robdo...@fastmail.fm

On 9/15/06, Robert Dockins <robdo...@fastmail.fm> wrote:

> You can define a direct fixed point combinator

> without relying on nominal recursion in Haskell, but it requires you to

> define a helper newtype.

> You can define a direct fixed point combinator

> without relying on nominal recursion in Haskell, but it requires you to

> define a helper newtype.

That's really nifty! I'd been wondering whether you could do this

too. Is there a reason for the extra `z' parameter?

> Don't run this in GHC because it will diverge. Hugs works, however.

According to

http://www.haskell.org/pipermail/glasgow-haskell-bugs/2001-August/001717.html

this is due to a bug in the GHC inliner that probably won't be fixed.

However, experimentation indicates you can work around the bug using

the NOINLINE pragma:

newtype Mu a = Roll { unroll :: Mu a -> a }

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

fix f = doink (Roll doink)

where {-# NOINLINE doink #-}

doink x = f ((unroll x) x)

Mike

Sep 15, 2006, 4:16:20 PM9/15/06

to Michael Shulman

On Friday 15 September 2006 14:48, Michael Shulman wrote:

> On 9/15/06, Robert Dockins <robdo...@fastmail.fm> wrote:

> > You can define a direct fixed point combinator

> > without relying on nominal recursion in Haskell, but it requires you to

> > define a helper newtype.

>

> That's really nifty! I'd been wondering whether you could do this

> too. Is there a reason for the extra `z' parameter?

> On 9/15/06, Robert Dockins <robdo...@fastmail.fm> wrote:

> > You can define a direct fixed point combinator

> > without relying on nominal recursion in Haskell, but it requires you to

> > define a helper newtype.

>

> That's really nifty! I'd been wondering whether you could do this

> too. Is there a reason for the extra `z' parameter?

It made the typing work out ;-) It can probably be eliminated, but I haven't

bothered to figure out how. I originally wrote it as a mental exercise and

stopped once I got it to work.

> > Don't run this in GHC because it will diverge. Hugs works, however.

>

> According to

>

> http://www.haskell.org/pipermail/glasgow-haskell-bugs/2001-August/001717.ht

>ml

>

> this is due to a bug in the GHC inliner that probably won't be fixed.

> However, experimentation indicates you can work around the bug using

> the NOINLINE pragma:

>

>

> newtype Mu a = Roll { unroll :: Mu a -> a }

>

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

> fix f = doink (Roll doink)

> where {-# NOINLINE doink #-}

> doink x = f ((unroll x) x)

>

>

> Mike

--

Rob Dockins

Talk softly and drive a Sherman tank.

Laugh hard, it's a long way to the bank.

-- TMBG

0 new messages

Search

Clear search

Close search

Google apps

Main menu