127 lines
3.1 KiB
Python
127 lines
3.1 KiB
Python
'''Population count'''
|
|
|
|
from functools import reduce
|
|
|
|
|
|
# popCount :: Int -> Int
|
|
def popCount(n):
|
|
'''The count of non-zero digits in the binary
|
|
representation of the positive integer n.'''
|
|
def go(x):
|
|
return Just(divmod(x, 2)) if 0 < x else Nothing()
|
|
return sum(unfoldl(go)(n))
|
|
|
|
|
|
# -------------------------- TEST --------------------------
|
|
def main():
|
|
'''Tests'''
|
|
|
|
print('Population count of first 30 powers of 3:')
|
|
print(' ' + showList(
|
|
[popCount(pow(3, x)) for x in enumFromTo(0)(29)]
|
|
))
|
|
|
|
evilNums, odiousNums = partition(
|
|
compose(even, popCount)
|
|
)(enumFromTo(0)(59))
|
|
|
|
print("\nFirst thirty 'evil' numbers:")
|
|
print(' ' + showList(evilNums))
|
|
|
|
print("\nFirst thirty 'odious' numbers:")
|
|
print(' ' + showList(odiousNums))
|
|
|
|
|
|
# ------------------------ GENERIC -------------------------
|
|
|
|
# Just :: a -> Maybe a
|
|
def Just(x):
|
|
'''Constructor for an inhabited Maybe (option type) value.
|
|
Wrapper containing the result of a computation.
|
|
'''
|
|
return {'type': 'Maybe', 'Nothing': False, 'Just': x}
|
|
|
|
|
|
# Nothing :: Maybe a
|
|
def Nothing():
|
|
'''Constructor for an empty Maybe (option type) value.
|
|
Empty wrapper returned where a computation is not possible.
|
|
'''
|
|
return {'type': 'Maybe', 'Nothing': True}
|
|
|
|
|
|
# compose :: ((a -> a), ...) -> (a -> a)
|
|
def compose(*fs):
|
|
'''Composition, from right to left,
|
|
of a series of functions.
|
|
'''
|
|
def go(f, g):
|
|
def fg(x):
|
|
return f(g(x))
|
|
return fg
|
|
return reduce(go, fs, lambda x: x)
|
|
|
|
|
|
# enumFromTo :: Int -> Int -> [Int]
|
|
def enumFromTo(m):
|
|
'''Enumeration of integer values [m..n]'''
|
|
return lambda n: range(m, 1 + n)
|
|
|
|
|
|
# even :: Int -> Bool
|
|
def even(x):
|
|
'''True if x is an integer
|
|
multiple of two.
|
|
'''
|
|
return 0 == x % 2
|
|
|
|
|
|
# partition :: (a -> Bool) -> [a] -> ([a], [a])
|
|
def partition(p):
|
|
'''The pair of lists of those elements in xs
|
|
which respectively do, and don't
|
|
satisfy the predicate p.
|
|
'''
|
|
|
|
def go(a, x):
|
|
ts, fs = a
|
|
return (ts + [x], fs) if p(x) else (ts, fs + [x])
|
|
return lambda xs: reduce(go, xs, ([], []))
|
|
|
|
|
|
# showList :: [a] -> String
|
|
def showList(xs):
|
|
'''Stringification of a list.'''
|
|
return '[' + ','.join(repr(x) for x in xs) + ']'
|
|
|
|
|
|
# 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()
|