Практика 7

Задания в классе

Тема занятия - Формулирование абстракций с помощью процедур высшего порядка.

На предыдущих занятиях мы строил абстракции на процедурах. То есть писали и тестировали некоторые процедуры, которые решали определенную задачу. Далее их могли бы использовать другие программисты в своих целях: определять простое ли число, искать сумму цифр числа. В итоге мы написали даже целую утилиту для шифра Виженера.

Но процедурной абстракции не достаточно для построения серьезных систем. Нужен еще один уровень - уровень абстракции процедур высшего порядка.

Рассмотрим следующие задачи:

Сумма чисел от 1 до N.
Сумма кубов чисел от 1 до N.
Сумма термов следующего вида: $\frac{1}{1 \cdot 3} + \frac{1}{5 \cdot 7} + \frac{1}{9 \cdot 11} + ... \to \frac{\pi}{8}$

Очевидно, что за этими задачами стоит одна общая абстракция - суммирование последовательностей. В математике мы знакомы с сигма нотацией, реализующей эту абстракцию: $\sum_{n=a}^b{f(n)} = f(a) + ... + f(b)$

Данная абстракция предполагает, что у нас есть некоторая процедура суммирования результатов некоторой другой процедуры. Для этого нам нужно уметь использовать функции в Python как переменные, и это возможно!

# Абстрагируем функцию возведения в квадрат.

def plus_one(x):
    return x + 1
def power2(function, x):
    return function(x) * function(x)

# Можем возводить в квадрату сумму    
power2(plus_one, 4) == (4+1)*(4+1) == 5*5 == 25
# lambda - это однострочная функция без имени
power2(lambda x: x*2, 4) == (4*2)*(4*2) == 8*8 == 64
# Длину строки!!
power2(lambda x: len(x), 'hello') == len('hello') * len('hello') == 5 * 5 == 25

Приступим к заданиям

Абстрактная сумма последовательности

$\sum_{n=a}^b{f(n)} = f(a) + ... + f(b)$

Контракт функции, который необходимо реализовать:

def summa(f, start, stop, step):
    """
    :param f: функция из 1 аргумента, которую нужно применить над каждым элементом
    :param start: начинаем сумму с числа start
    :param step: ссылка на функцию которая возвращает следующее число
    :param stop: заканчиваем суммирование на числе stop
    """
    return 0

# Пример использования - сумма остатков от деления на три каждого второго числа от 1 до 100
summa(lambda x: x % 3, 1, 100, lambda x: x + 2)

# Сумма квадратов чисел от 1 до 5
summa(lambda x: x**2, 1, 5, lambda x: x + 1) == 1**1 + 2**2 + 3**2 + 4**2

Далее напишите вычисление числа $\pi$ используя формулу из начала практики и абстрактуню сумму.

Абстракция накопления данных

Кроме суммы у нас существует еще и проивзедение элементов последовательностей. Абстракцией над этими частными случаями является общее понятие Накопление.

Тогда получаем следуюущую сигнатуру метода:

def accumulate(combiner, initial_value, f, start, stop, step):
    """
    :param combiner: функция из 2 аргументов, которая указывает как присоединить текущее значение к уже накопленным
    :param initial_value: значение с которого всё начинается. Для суммы это 0, а для произведения - 1.
    :param f: функция из 1 аргумента, которую нужно применить над каждым элементом
    """
    return 0

# сумма квадратов чисел от 0 до 10
accumulate(lambda acc, cur: acc + cur, 0, lambda x: x**2, 1, 10, lambda i: i + 1)

Используя эту абстракцию напишите возведение в квадрат четных чисел от 2 до 10.

$2 ^ {4 ^ {6 ^ {8 ^ {10}}}}$

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

Не забывайте про тесты.

Фильтрующий аккумулятор

К нашей абстракции накопления можно добавить еще и фильтрацию. Тогда мы будем накапливать только те элементы, которые удовлетворяют некоторому условию. Добавим еще один аругмент predicate - ссылку на функцию, принимающую 1 аргумент и возвращающую True/False

def filtered_accumulate(combiner, initial_value, predicate, f, start, stop, step):
    return 0

filtered_accumulate(lambda acc, cur: acc + cur, 10, lambda x: x % 10 == 6, lambda x: x, 1, 1025, lambda i: i*2) == 10 + 16 + 256

С помощью этой абстракции выразите следующее:

Сумма квадратов простых чисел в диапазоне от a до b.
Произведение суммы цифр чисел последовательности $i^2$ : [1, 4, 9, 16, 25, 36, 49, ...] -> [1, 4, 9, 7, 7, 9, 13, ...] -> 1*4*9*7*7*9*13*....
Сложная дополнительная задача на много баллов. Перепишите предыдущую функцию так, чтобы она использовала предикат, как пост-условие. То есть оно будет проверяться после применения функции f над элементом последовательности. Решите задачу: Создание строки английских букв, кроме гласных букв, из букв алфавита, полученных из суммы цифр чисел последовательности Фибоначчи до 1000(имеется ввиду не 1000 номеров фибоначчи, а N чисел фибоначчи, которые не превышают 1000). Если полученный ASCII код не входит в диапазон английских букв, то верните его в него. Предполагается, что здесь вам нужно будет написать функцию step таким образом, чтобы она возвращала вам числа фибоначчи. filtered-accumulate(combiner, "", predicate, f, 1, 1000, next_fib_number) == "bbcdfdhkrjrhy". То есть есть [1 1 2 3 5 8 13 21] -> [1 1 2 3 5 8 4 3] -> [b b c d f i e d] -> [b b c d f d] -> 'bbcdfd'. Алгоритм должен работать эффективно, то есть числа фибоначчи не должны вычисляться каждйы раз заново.

Hints

Читайте главу 1.3 из учебника “Структура и интерпретация компьютерных программ”.

Читайте конспект лекций про функциональные коллекции, чтобы понять зачем это нужно MIT 6.005 - Map Filter Reduce.