84 lines
2.2 KiB
Python
84 lines
2.2 KiB
Python
'''Quotient and remainder of division by the Rhind papyrus method.'''
|
|
|
|
from functools import reduce
|
|
|
|
|
|
# eqyptianQuotRem :: Int -> Int -> (Int, Int)
|
|
def eqyptianQuotRem(m):
|
|
'''Quotient and remainder derived by the Eqyptian method.'''
|
|
|
|
def expansion(xi):
|
|
'''Doubled value, and next power of two - both by self addition.'''
|
|
x, i = xi
|
|
return Nothing() if x > m else Just(
|
|
((x + x, i + i), xi)
|
|
)
|
|
|
|
def collapse(qr, ix):
|
|
'''Addition of a power of two to the quotient,
|
|
and subtraction of a paired value from the remainder.'''
|
|
i, x = ix
|
|
q, r = qr
|
|
return (q + i, r - x) if x < r else qr
|
|
|
|
return lambda n: reduce(
|
|
collapse,
|
|
unfoldl(expansion)(
|
|
(1, n)
|
|
),
|
|
(0, m)
|
|
)
|
|
|
|
|
|
# ------------------------- TEST --------------------------
|
|
# main :: IO ()
|
|
def main():
|
|
'''Test'''
|
|
print(
|
|
eqyptianQuotRem(580)(34)
|
|
)
|
|
|
|
|
|
# ------------------- GENERIC FUNCTIONS -------------------
|
|
|
|
# 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}
|
|
|
|
|
|
# unfoldl(lambda x: Just(((x - 1), x)) if 0 != x else Nothing())(10)
|
|
# -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
|
|
# unfoldl :: (b -> Maybe (b, a)) -> b -> [a]
|
|
def unfoldl(f):
|
|
'''Dual to reduce or foldl.
|
|
Where these reduce a list to a summary value, unfoldl
|
|
builds a list from a seed value.
|
|
Where f returns Just(a, b), a is appended to the list,
|
|
and the residual b is used as the argument for the next
|
|
application of f.
|
|
When f returns Nothing, the completed list is returned.
|
|
'''
|
|
def go(v):
|
|
x, r = v, v
|
|
xs = []
|
|
while True:
|
|
mb = f(x)
|
|
if mb.get('Nothing'):
|
|
return xs
|
|
else:
|
|
x, r = mb.get('Just')
|
|
xs.insert(0, r)
|
|
return xs
|
|
return go
|
|
|
|
|
|
# MAIN ----------------------------------------------------
|
|
if __name__ == '__main__':
|
|
main()
|