Stern-Brocot sequence: Difference between revisions

Content added Content deleted
(Added 11l)
Line 3,937: Line 3,937:
<lang python>'''Stern-Brocot sequence'''
<lang python>'''Stern-Brocot sequence'''


⚫
import math
⚫
from itertools import (count, dropwhile, islice, takewhile)
import operator
import operator
⚫
from itertools import chain, count, dropwhile, islice, takewhile
⚫
import math




Line 3,949: Line 3,949:
def go(xs):
def go(xs):
x = xs[1]
x = xs[1]
return (tail(xs) + [x + head(xs), x])
return (x, tail(xs) + [x + head(xs), x])
return fmapGen(head)(
return chain([1], unfoldr(go)([1, 1]))
iterate(go)([1, 1])
⚫
)



⚫
# TESTS ---------------------------------------------------


⚫
# ------------------------ TESTS -------------------------
# main :: IO ()
# main :: IO ()
def main():
def main():
Line 3,998: Line 3,995:




# GENERIC ABSTRACTIONS ------------------------------------
# ----------------- GENERIC ABSTRACTIONS -----------------



# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
Line 4,027: Line 4,023:
'''True if p(x) holds for every x in xs'''
'''True if p(x) holds for every x in xs'''
return lambda xs: all(map(p, xs))
return lambda xs: all(map(p, xs))


⚫
# fmapGen <$> :: (a -> b) -> Gen [a] -> Gen [b]
⚫
def fmapGen(f):
'''A function f mapped over a
non finite stream of values.'''
⚫
def go(g):
⚫
while True:
v = next(g, None)
if None is not v:
⚫
yield f(v)
else:
return
⚫
return lambda gen: go(gen)




Line 4,053: Line 4,035:
'''The first element of a non-empty list.'''
'''The first element of a non-empty list.'''
return xs[0]
return xs[0]


# 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)




Line 4,071: Line 4,041:
'''A sublist of xs from which all duplicates,
'''A sublist of xs from which all duplicates,
(as defined by the equality predicate p)
(as defined by the equality predicate p)
are excluded.'''
are excluded.
⚫
'''
def go(xs):
def go(xs):
if not xs:
if not xs:
Line 4,082: Line 4,053:
))
))
)
)
return lambda xs: go(xs)
return go




Line 4,100: Line 4,071:
return xs[1:]
return xs[1:]
else:
else:
list(islice(xs, 1)) # First item dropped.
islice(xs, 1) # First item dropped.
return xs
return xs


Line 4,114: Line 4,085:
else list(islice(xs, n))
else list(islice(xs, n))
)
)


⚫
# unfoldr :: (b -> Maybe (a, b)) -> b -> Gen [a]
⚫
def unfoldr(f):
'''A lazy (generator) list unfolded from a seed value
by repeated application of f until no residue remains.
Dual to fold/reduce.
f returns either None or just (value, residue).
For a strict output list, wrap the result with list()
'''
⚫
def go(x):
⚫
valueResidue = f(x)
⚫
while valueResidue:
⚫
yield valueResidue[0]
valueResidue = f(valueResidue[1])
⚫
return go




Retrieved from "https://rosettacode.org/wiki/Stern-Brocot_sequence"