seemingly_impossible.py

# see http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/


def cons(head, tail):
    def out(i):
        if i == 0:
            return head
        else:
            return tail(i - 1)

    return out


all_ones = lambda _: 1

all_zeros = lambda _: 0

every_other = lambda i: i % 2


def print_stream(f):
    [print(f(x), end=", ") for x in range(10)]
    print("...")


print_stream(all_ones)
print_stream(all_zeros)
print_stream(cons(1, all_zeros))
print_stream(every_other)


def for_some(pred):
    return pred(find(lambda a: pred(a)))


def find(pred):
    def wrap(i):
        # print(i)
        if for_some(lambda a: pred(cons(0, a))):  # needs to be lazy!
            return cons(0, find(lambda a: pred(cons(0, a))))(i)
        else:
            return cons(1, find(lambda a: pred(cons(1, a))))(i)

    return wrap


def for_every(pred):
    return not for_some(lambda a: not pred(a))


# print(for_every(lambda _: False))
# print(for_every(lambda _: True))
# print(for_every(lambda stream: stream(3) == 1))


def equal(f, g):
    return for_every(lambda a: f(a) == g(a))


print(equal(lambda stream: stream(3) == 1, lambda stream: stream(3) == 1))
# print(equal(lambda stream: stream(3) == 1, lambda stream: stream(4) == 1))


# find(lambda _: False)(4)
# print_stream(find(lambda _: False))
# print_stream(find(lambda _: True))
# print_stream(find(lambda stream: stream(3) == 1))
# # print_stream(find(lambda _: False))