Cycle detection: Difference between revisions
→{{header|Python}}: First draft of a functional solution (recursive ...)
Alextretyak (talk | contribs) (Added 11l) |
(→{{header|Python}}: First draft of a functional solution (recursive ...)) |
||
Line 1,221:
=={{header|Python}}==
===Procedural===
Function from the Wikipedia article:
<lang python>import itertools
Line 1,320 ⟶ 1,321:
print("Cycle: %s" % list(itertools.islice(iterate(f, x0), mu, mu+lam)))</lang>
{{out}}
<pre>Cycle length: 6
Cycle start index: 2
Cycle: [101, 2, 5, 26, 167, 95]</pre>
===Functional===
In functional terms, the problem lends itself at first sight (see the Haskell version), to a reasonably compact recursive definition of a ''cycleLength'' function:
{{Trans|Haskell}}
{{Works with|Python|3.7}}
<lang python>'''Cycle detection'''
from itertools import (chain, cycle, islice)
from operator import (eq)
# cycleFound :: Eq a => [a] -> Maybe ([a], Int, Int)
def cycleFound(xs):
'''Just the first cycle found, with its length
and start index, or Nothing if no cycle seen.
'''
return bind(cycleLength(xs))(
lambda n: bind(
findIndex(uncurry(eq))(zip(xs, xs[n:]))
)(lambda iStart: Just(
(xs[iStart:iStart + n], n, iStart)
))
)
# cycleLength :: Eq a => [a] -> Maybe Int
def cycleLength(xs):
'''Just the length of the first cycle found,
or Nothing if no cycle seen.
'''
def go(pwr, lng, x, ys):
if ys:
y, *yt = ys
return Just(lng) if x == y else (
go(2 * pwr, 1, y, yt) if (
lng == pwr
) else go(pwr, 1 + lng, x, yt)
)
else:
return Nothing()
return go(1, 1, xs[0], xs[1:]) if xs else Nothing()
# TEST ----------------------------------------------------
# main :: IO ()
def main():
'''Reports of any cycle detection.'''
print(
fTable(
'First cycle detected, if any:\n'
)(fst)(maybe('No cycle found')(
showCycle
))(
compose(cycleFound)(snd)
)([
(
'cycle([1, 2, 3])',
take(1000)(cycle([1, 2, 3]))
), (
'[0..100] + cycle([1..8])',
take(1000)(
chain(
enumFromTo(0)(100),
cycle(enumFromTo(1)(8))
)
)
), (
'[1..500]',
enumFromTo(1)(500)
), (
'f(x) = (x*x + 1) modulo 255',
take(1000)(iterate(
lambda x: (1 + (x * x)) % 255
)(3))
)
])
)
# DISPLAY -------------------------------------------------
# showList :: [a] -> String
def showList(xs):
''''Compact stringification of a list,
(no spaces after commas).
'''
return ''.join(repr(xs).split())
# showCycle :: ([a], Int, Int) -> String
def showCycle(cli):
'''Stringification of cycleFound tuple.'''
c, lng, iStart = cli
return showList(c) + ' (from:' + str(iStart) + (
', length:' + str(lng) + ')'
)
# GENERIC -------------------------------------------------
# Just :: a -> Maybe a
def Just(x):
'''Constructor for an inhabited Maybe (option type) value.'''
return {'type': 'Maybe', 'Nothing': False, 'Just': x}
# Nothing :: Maybe a
def Nothing():
'''Constructor for an empty Maybe (option type) value.'''
return {'type': 'Maybe', 'Nothing': True}
# bind (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
def bind(m):
'''bindMay provides the mechanism for composing a
sequence of (a -> Maybe b) functions.
If m is Nothing, it is passed straight through.
If m is Just(x), the result is an application
of the (a -> Maybe b) function (mf) to x.'''
return lambda mf: (
m if m.get('Nothing') else mf(m.get('Just'))
)
# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
def compose(g):
'''Right to left function composition.'''
return lambda f: lambda x: g(f(x))
# enumFromTo :: (Int, Int) -> [Int]
def enumFromTo(m):
'''Integer enumeration from m to n.'''
return lambda n: list(range(m, 1 + n))
# findIndex :: (a -> Bool) -> [a] -> Maybe Int
def findIndex(p):
'''Just the first index at which an
element in xs matches p,
or Nothing if no elements match.'''
def go(xs):
try:
return Just(next(
i for i, x in enumerate(xs) if p(x)
))
except StopIteration:
return Nothing()
return lambda xs: go(xs)
# fst :: (a, b) -> a
def fst(tpl):
'''First member of a pair.'''
return tpl[0]
# fTable :: String -> (a -> String) ->
# (b -> String) ->
# (a -> b) -> [a] -> String
def fTable(s):
'''Heading -> x display function -> fx display function ->
f -> value list -> tabular string.'''
def go(xShow, fxShow, f, xs):
w = max(map(compose(len)(xShow), xs))
return s + '\n' + '\n'.join([
xShow(x).rjust(w, ' ') + ' -> ' + fxShow(f(x)) for x in xs
])
return lambda xShow: lambda fxShow: (
lambda f: lambda xs: go(
xShow, fxShow, f, xs
)
)
# iterate :: (a -> a) -> a -> Gen [a]
def iterate(f):
'''An infinite list of repeated
applications of f to x.'''
def go(x):
v = x
while True:
yield v
v = f(v)
return lambda x: go(x)
# maybe :: b -> (a -> b) -> Maybe a -> b
def maybe(v):
'''Either the default value v, if m is Nothing,
or the application of f to x,
where m is Just(x).'''
return lambda f: lambda m: v if m.get('Nothing') else (
f(m.get('Just'))
)
# snd :: (a, b) -> b
def snd(tpl):
'''Second member of a pair.'''
return tpl[1]
# take :: Int -> [a] -> [a]
# take :: Int -> String -> String
def take(n):
'''The prefix of xs of length n,
or xs itself if n > length xs.'''
return lambda xs: (
xs[0:n]
if isinstance(xs, list)
else list(islice(xs, n))
)
# uncurry :: (a -> b -> c) -> ((a, b) -> c)
def uncurry(f):
'''A function over a tuple
derived from a default or
curried function.'''
return lambda xy: f(xy[0], xy[1])
# concat :: [[a]] -> [a]
# concat :: [String] -> String
def concat(xxs):
'''The concatenation of all the elements in a list.'''
xs = list(chain.from_iterable(xxs))
unit = '' if isinstance(xs, str) else []
return unit if not xs else (
''.join(xs) if isinstance(xs[0], str) else xs
)
# MAIN ---
if __name__ == '__main__':
main()</lang>
{{Out}}
<pre>First cycle detected, if any:
cycle([1, 2, 3]) -> [1,2,3] (from:0, length:3)
[0..100] + cycle([1..8]) -> [1,2,3,4,5,6,7,8] (from:101, length:8)
[1..500] -> No cycle found
f(x) = (x*x + 1) modulo 255 -> [101,2,5,26,167,95] (from:2, length:6)</pre>
=={{header|Racket}}==
| |||