Cycle detection: Difference between revisions
→Functional Python: Refactoring cycleLength in terms of until, then reimplementing until as iterative
(→{{header|Python}}: First draft of a functional solution (recursive ...)) |
(→Functional Python: Refactoring cycleLength in terms of until, then reimplementing until as iterative) |
||
Line 1,570:
[1..500] -> No cycle found
f(x) = (x*x + 1) modulo 255 -> [101,2,5,26,167,95] (from:2, length:6)</pre>
But recursion scales poorly in Python, and the version above, while good for lists of a few hundred elements, will need refactoring for longer lists and better use of space.
If we start by refactoring the recursion into the form of a higher order (but still recursive) '''until(p)(f)(x)''' function, we can then reimplement the internals of until itself to avoid recursion, without losing the benefits of compositional structure:
Recursive ''until'':
<lang python># until :: (a -> Bool) -> (a -> a) -> a -> a
def until(p):
'''The result of repeatedly applying f until p holds.
The initial seed value is x.'''
def go(f, x):
return x if p(x) else go(f, f(x))
return lambda f: lambda x: go(f, x)</lang>
''cycleLength'' refactored in terms of ''until'':
<lang python># cycleLength :: Eq a => [a] -> Maybe Int
def cycleLength(xs):
'''Just the length of the first cycle found,
or Nothing if no cycle seen.'''
# f :: (Int, Int, Int, [Int]) -> (Int, Int, Int, [Int])
def f(tpl):
pwr, lng, x, ys = tpl
y, *yt = ys
return (2 * pwr, 1, y, yt) if (
lng == pwr
) else (pwr, 1 + lng, x, yt)
# p :: (Int, Int, Int, [Int]) -> Bool
def p(tpl):
_, _, x, ys = tpl
return (not ys) or x == ys[0]
if xs:
_, lng, x, ys = until(p)(f)(
(1, 1, xs[0], xs[1:])
)
return (
Just(lng) if (x == ys[0]) else Nothing()
) if ys else Nothing()
else:
return Nothing()</lang>
Iterative reimplementation of ''until'':
<lang python># until_ :: (a -> Bool) -> (a -> a) -> a -> a
def until_(p):
'''The result of repeatedly applying f until p holds.
The initial seed value is x.'''
def go(f, x):
v = x
while not p(v):
v = f(v)
return v
return lambda f: lambda x: go(f, x)</lang>
=={{header|Racket}}==
| |||