[Haskell-cafe] Detecting Cycles in Datastructures
gregory.woodhouse at sbcglobal.net
Fri Nov 18 20:16:47 EST 2005
--- 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
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)
(65 reductions, 95 cells)
Main> take 2 (fix h)
(96 reductions, 138 cells)
Main> take 3 (fix h)
(123 reductions, 178 cells)
Main> take 4 (fix h)
(150 reductions, 218 cells)
Main> take 5 (fix h)
(177 reductions, 258 cells)
Main> take 6 (fix h)
(204 reductions, 298 cells)
(In case it's not obvious, I'm a complete Haskell newbie, and find this
Gregory Woodhouse <gregory.woodhouse at sbcglobal.net>
"Interaction is the mind-body problem of computing."
More information about the Haskell-Cafe