U-курс

Домашнее задание № 2

Для выполнения задания найди ссылку-приглашение в онлайн чате, получи доступ к репозиторию с файлом-заготовкой и заполни пропуски в нём. Фиксируй изменения (делай коммиты) после решения каждой задачи. Оставь название файла неизменным, иначе робот-проверятель не найдёт твои ответы. Отправить решения на GitHub нужно до истечения установленного срока.

Некоторые доктесты будут ссылаются на эти функции.

from operator import add, mul, sub

square = lambda x: x * x
identity = lambda x: x
triple = lambda x: 3 * x
increment = lambda x: x + 1

После завершения работы над каждым вопросом требуется фиксировать изменения (делать коммит), сопровождая его вменяемым описанием сделанного, например:

$ git add .
$ git commit -m "Решение вопроса X"

Так же не возбраняется в любое время проталкивать изменения на GitHub:

$ git push

Вопрос 1

В лекции «Функции высшего порядка» была рассмотрена функция summation(n, term), результат её выполнения — term(1) + … + term(n). Напиши похожую функцию product(n, term), которая возвращает term(1) * … * term(n). Использовать рекурсию нельзя.

def product(n, term):
    """
    Возвращает произведение первых n членов (terms) последовательности.

    Аргументы:
        n (int): количество перемножаемых элементов последовательности.
        term (func): функция одного аргумента.

    >>> product(3, identity)  # 1 * 2 * 3
    6
    >>> product(5, identity)  # 1 * 2 * 3 * 4 * 5
    120
    >>> product(3, square)    # 1^2 * 2^2 * 3^2
    36
    >>> product(5, square)    # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
    14400
    >>> product(3, increment) # (1+1) * (2+1) * (3+1)
    24
    >>> product(3, triple)    # 1*3 * 2*3 * 3*3
    162
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Теперь покажи, как определить функцию factorial в одну строчку, используя функцию product.

def factorial(n):
    """
    Возвращает факториал n при n >= 0, используя функцию product.

    >>> factorial(4)  # 4 * 3 * 2 * 1
    24
    >>> factorial(6)  # 6 * 5 * 4 * 3 * 2 * 1
    720
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 2

На самом деле и summation, и product — частные случаи более общей функции accumulate (накопление).

def accumulate(combiner, base, n, term):
    """
    Возвращает результат объединения (combining) первых n членов последовательности.

    >>> accumulate(add, 0, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
    15
    >>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
    26
    >>> accumulate(add, 11, 0, identity) # 11
    11
    >>> accumulate(add, 11, 3, square)   # 11 + 1^2 + 2^2 + 3^2
    25
    >>> accumulate(mul, 2, 3, square)    # 2 * 1^2 * 2^2 * 3^2
    72
    >>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
    19
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Функция accumulate принимает следующие аргументы:

term и n — те же, что в функциях summation и product;
combiner — функция двух аргументов, которая определяет, как один член объединяется с другим;
base — значение, с которого начинается накопление.

Например, accumulate(add, 11, 3, square) — это 11 + square(1) + square(2) + square(3) = 25

Можешь считать, что combiner обладает ассоциативностью и коммутативностью, то есть combiner(a, combiner(b, c)) == combiner(combiner(a, b), c) и combiner(a, b) == combiner(b, a) для всех a, b и c. Однако нельзя считать, что поведение combiner выбирается из фиксированного набора действий.

Реализуй accumulate, а потом покажи, как summation и product могут быть определены через вызов accumulate.

def summation_using_accumulate(n, term):
    """
    Возвращает сумму term(1) + ... + term(n). Реализация с использованием accumulate.

    >>> summation_using_accumulate(5, square)
    55
    >>> summation_using_accumulate(5, triple)
    45
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

def product_using_accumulate(n, term):
    """
    Возвращает произведение term(1) * ... * term(n). Реализация с использованием accumulate.

    >>> product_using_accumulate(3, lambda x: (x+1)*(x+5)*x)
    48384
    >>> product_using_accumulate(4, square)
    576
    >>> product_using_accumulate(6, triple)
    524880
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 3

Допиши функцию double, которая принимает одну функцию, а возвращает другую функцию, применяющую первоначальную функцию дважды. Например, если функция inc возвращает увеличенное на единицу значение аргумента, то результат double(inc) должен быть функцией, увеличивающей значение аргумента на два.

def double(f):
    """
    Возвращает функцию, применяющую f дважды.

    Аргументы:
        f (func): функция одного аргумента.

    >>> double(square)(2)
    16
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 4

Напиши функцию make_repeater, чтобы вызов make_repeater(f, n)(x) возвращал результат f(f(…f(x)…)), в котором f применяется n раз. То есть make_repeater(f, n) должен вернуть новую функцию одного аргумента. Например, результат make_repeater(square, 3)(42) можно представить как square(square(square(42))).

def make_repeater(f, n):
    """Возвращает функцию, применяющую f n раз.

    Аргументы:
        f (func): функция одного аргумента.
        n (int): количество применений функции f.

    >>> add_three = make_repeater(increment, 3)
    >>> add_three(5)
    8
    >>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
    243
    >>> make_repeater(square, 2)(5) # square(square(5))
    625
    >>> make_repeater(square, 4)(5) # square(square(square(square(5))))
    152587890625
    >>> make_repeater(square, 0)(5) # Да, применение функции ноль раз тоже имеет смысл!
    5
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

В качестве дополнительно упражнения реализуй make_repeater в одну строку (return …), используя функции compose1 (из лекции) и accumulate (из второго вопроса).

def compose1(f, g):
    """Возвращает функцию h такую, что h(x) = f(g(x))."""
    def h(x):
        return f(g(x))
    return h

Вопрос 5* (для самых умных)

Учёный-логик Алонзо Чёрч изобрел систему представления неотрицательных чисел исключительно с помощью функций. Цель состояла в том, чтобы показать, что функций достаточно для описания всей теории чисел: если у нас есть функции, нам не нужно полагать, что числа существуют — вместо этого мы можем их сконструировать.

Задачи «для самых умных» опциональны. Попробуй порешать. Не выходит — и не надо.

Твоя же цель состоит в освоении представления, известного как «Числа Чёрча». Вот определение для нулевого числа Чёрча zero и функции successor, увеличивающей число Чёрча на единицу:

def zero(f):
    return lambda x: x

def successor(n):
    return lambda f: lambda x: f(n(f)(x))

Определи единицу one и двойку two так, чтобы их поведение было successor(zero) и successsor(successor(zero)) соответственно. Однако не используй successor в своём коде.

Далее определи функцию church_to_int — преобразование числа Чёрча в обычное целочисленное представление.

Наконец, реализуй для чисел Чёрча сложение add_church, умножение mul_church и возведение в степень pow_church.

def one(f):
    """Число Чёрча 1."""
    "*** ТВОЙ КОД ЗДЕСЬ ***"

def two(f):
    """Число Чёрча 2."""
    "*** ТВОЙ КОД ЗДЕСЬ ***"

three = successor(two)

def church_to_int(n):
    """Преобразует число Чёрча n в целое число Python.

    >>> church_to_int(zero)
    0
    >>> church_to_int(one)
    1
    >>> church_to_int(two)
    2
    >>> church_to_int(three)
    3
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

def add_church(m, n):
    """Возвращает число Чёрча m + n для чисел Чёрча m и n.

    >>> church_to_int(add_church(two, three))
    5
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

def mul_church(m, n):
    """Возвращает число Чёрча m * n для чисел Чёрча m и n.

    >>> four = successor(three)
    >>> church_to_int(mul_church(two, three))
    6
    >>> church_to_int(mul_church(three, four))
    12
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

def pow_church(m, n):
    """Возвращает число Чёрча m ** n для чисел Чёрча m и n.

    >>> church_to_int(pow_church(two, three))
    8
    >>> church_to_int(pow_church(three, two))
    9
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Не забудь отправить работу на проверку:

$ git add .
$ git commit -m "Окончательное решение"
$ git push