[Haskell-cafe] Detecting Cycles in Datastructures

[Greg Woodhouse]

--- jerzy.karczmarczuk at info.unicaen.fr wrote:

> 
> fix f = f (fix f)   -- Here you have your Y. No typeless lambda.
> 
> g f n = n : f n    -- This is a generic *non-recursive* `repeat`
> ones = fix g 1     -- Guess what.
> 
> 

Very nice! I honestly would not have expected this to work. Simple
cases of lazy evaluation are one thing, but this is impressive.

Incidentally, I only(!) have accces to Hugs here in the office, but
defining

fix f         = f (fix f)
g f n         = n : f n
h f           = 1 : map (+1) f

I see that the number of reductions required for each successive term
in h actually seems to go down.

Main> take 1 (fix h)
[1]
(65 reductions, 95 cells)
Main> take 2 (fix h)
[1,2]
(96 reductions, 138 cells)
Main> take 3 (fix h)
[1,2,3]
(123 reductions, 178 cells)
Main> take 4 (fix h)
[1,2,3,4]
(150 reductions, 218 cells)
Main> take 5 (fix h)
[1,2,3,4,5]
(177 reductions, 258 cells)
Main> take 6 (fix h)
[1,2,3,4,5,6]
(204 reductions, 298 cells)

(In case it's not obvious, I'm a complete Haskell newbie, and find this
rather impressive.)
Main>                            


===
Gregory Woodhouse  <gregory.woodhouse at sbcglobal.net>


"Interaction is the mind-body problem of computing."

--Philip Wadler