#!/usr/bin/env python3

from operator import add


def map_t(fn):
    def trans(reducer):
        def result(acc, input):
            return reducer(acc, fn(input))

        return result

    return trans


def filter_t(pred):
    def trans(reducer):
        def result(acc, input):
            if pred(input):
                return reducer(acc, input)
            else:
                return acc

        return result

    return trans


def take_t(n):
    def trans(reducer):
        def result(acc, input):
            nonlocal n
            if n:
                n -= 1
                return reducer(acc, input)
            else:
                return acc

        return result

    return trans


def comp(a, b):
    def result(n):
        return a(b(n))

    return result


def compn(*fns):
    return transduce(id, comp, id, fns)


def transduce(xform, f, init, coll):
    reducer = xform(f)
    acc = init
    for x in coll:
        acc = reducer(acc, x)
    return acc


def main():
    assert transduce(map_t(inc), append, [], range(5)) == [1, 2, 3, 4, 5]

    assert transduce(filter_t(odd), append, [], range(10)) == [1, 3, 5, 7, 9]

    assert transduce(id, add, 0, range(1, 6)) == 15

    xf = compn(filter_t(odd), map_t(inc))

    assert transduce(xf, append, [], [1, 2, 3, 4, 5]) == [2, 4, 6]

    assert transduce(xf, add, 0, range(5)) == 6

    assert transduce(take_t(3), append, [], [1, 2, 3, 4]) == [1, 2, 3]


def append(coll, x):
    return [*coll, x]


def id(x):
    return x


def inc(n):
    return n + 1


def odd(n):
    return n % 2 != 0


if __name__ == "__main__":
    main()