100 lines
2.2 KiB
Python
100 lines
2.2 KiB
Python
'''Van Eck sequence'''
|
|
|
|
from functools import reduce
|
|
from itertools import repeat
|
|
|
|
|
|
# vanEck :: Int -> [Int]
|
|
def vanEck(n):
|
|
'''First n terms of the van Eck sequence.'''
|
|
|
|
return churchNumeral(n)(
|
|
lambda xs: cons(
|
|
maybe(0)(succ)(
|
|
elemIndex(xs[0])(xs[1:])
|
|
)
|
|
)(xs) if xs else [0]
|
|
)([])[::-1]
|
|
|
|
|
|
# TEST ----------------------------------------------------
|
|
def main():
|
|
'''Terms of the Van Eck sequence'''
|
|
print(
|
|
main.__doc__ + ':\n\n' +
|
|
'First 10: '.rjust(18, ' ') + repr(vanEck(10)) + '\n' +
|
|
'991 - 1000: '.rjust(18, ' ') + repr(vanEck(1000)[990:])
|
|
)
|
|
|
|
|
|
# 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}
|
|
|
|
|
|
# churchNumeral :: Int -> (a -> a) -> a -> a
|
|
def churchNumeral(n):
|
|
'''n applications of a function
|
|
'''
|
|
return lambda f: lambda x: reduce(
|
|
lambda a, g: g(a), repeat(f, n), x
|
|
)
|
|
|
|
|
|
# cons :: a -> [a] -> [a]
|
|
def cons(x):
|
|
'''Construction of a list from a head and a tail.
|
|
'''
|
|
return lambda xs: [x] + xs
|
|
|
|
|
|
# elemIndex :: Eq a => a -> [a] -> Maybe Int
|
|
def elemIndex(x):
|
|
'''Just the index of the first element in xs
|
|
which is equal to x,
|
|
or Nothing if there is no such element.
|
|
'''
|
|
def go(xs):
|
|
try:
|
|
return Just(xs.index(x))
|
|
except ValueError:
|
|
return Nothing()
|
|
return go
|
|
|
|
|
|
# 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 None is m or m.get('Nothing') else (
|
|
f(m.get('Just'))
|
|
)
|
|
|
|
|
|
# succ :: Enum a => a -> a
|
|
def succ(x):
|
|
'''The successor of a value.
|
|
For numeric types, (1 +).
|
|
'''
|
|
return 1 + x
|
|
|
|
|
|
# MAIN ---
|
|
if __name__ == '__main__':
|
|
main()
|