# Re[Haskell-cafe] cursive referencing

Eugene Kirpichov ekirpichov at gmail.com
Thu Jan 29 03:44:57 EST 2009

```Пожалуйста :)

It's difficult to do this in lambda because it isn't expressible in
simply (or even polymorphically) typed lambda calculus, since it
requires the Y (fix) combinator, which introduces non-terminating
computations, whereas simply- and polymorphically-typed lambda
calcules are strongly normalizing (all computations terminate).
So, you can't write *simple and intuitive* typed code for this in lambda.

To express it, you either need untyped lambda or Haskell, where the
'fix' combinator is typed by kind of a hack :)

With the Y combinator, the code becomes as follows:

f = \somedata1 somedata2 -> fst \$ fix (\(aa,bb) -> (AA somedata1 bb,
BB somedata2 aa))

I tried to prove to myself that the structure really turns out cyclic,
but games with reallyUnsafePtrEquality# didn't lead to success; that's
why it's "reallyUnsafe" :-/

2009/1/29 Belka <lambda-belka at yandex.ru>:
>
>>Yes.
>>f somedata1 somedata2 = aa
>>  where aa = AA somedata1 bb
>>            bb = BB somedata2 aa
>
> Spasibo, Yevgeny!
>
> Originally I was thinking theoretically about a single plain
> lambda-expression, like
> (\ somedata1 somedata2 ->
>    (\ aa bb -> aa (bb aa))
>          (\ b -> AA somedata1 b)
>          (\ a -> BB somedata2 a)
> )
> But in the code "aa (bb aa)" last aa stays lacking an argument, of course,
> if we don't consider 1st application "aa (" as having a side effect on aa.
> And that's where "separate and rule" shows up it's power (speaking about
> "where" and namespacing in general). =)
>
> Belka
> --
> View this message in context: http://www.nabble.com/Recursive-referencing-tp21722002p21722503.html
> Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
>
> _______________________________________________
> Haskell-Cafe mailing list