10.01 Функции и замыкание

• Функция как именованная запись алгоритма
  • duck typing
  • пространство имён и pythontutor.com
    • вызов одной функции из другой

    • написать примитивно-рекурсивную функцию на 4 вызова, пронаблюдать как она работает

  • Задача_0: поиск Парето-фронта в двумерном пространстве

  • лямбда-функции (функции-выражения)

    • как работает sorted(…, key=fun)

    • переписать Задачу_2 из прошлого семинара в однострочник с использованием sorted():

      • ввести и отсортировать по возрастанию ключей числовой список, в качестве ключа сравнения использовать остаток от деления x2 на 100

  • Задача_1: написать функцию вычитания двух объектов

  • Задача_2: Реализовать рекурсивную функцию бинарного поиска (проверки наличия) элемента в упорядоченной по неубыванию индексируемой хранимой последовательности.

• Замыкание: как образуется, почему изнутри это не так просто, как снаружи?
  • Разбор примера про adder-ы из лекций

• Функционал: на вход две функции от одной переменной (f(x) и g(x)) , на выходе — функция от одной переменой h(x)=f(x)+g(x)

• Задача_3: Функционал-еval()-ище.

Задачи

0. Поиск Парето-фронта в двумерном пространстве

   • пара (x,y) доминируется парой (a,b), если x<=a, y<=b, и верно хотя бы одно из: x<a, y<b

   • написать функцию Pareto, которая:
     • получает на вход набор пар чисел, количество пар заранее не известно
     • находит Парето-фронт, т.е. все пары из заданного набора, каждая из которых не доминируется никакой парой из заданного набора
     • возвращает результат в виде кортежа из найденных пар чисел
   • функция должна поддерживать вызов в формате Pareto(pair_1, pair_2, pair_3, ...), где pair_i -- кортеж из двух чисел
   • допустимо решать задачу путем прохода по набору пар и проверки, доминируется ли очередная пара какой-либо из других пар

      1 >>> Pareto((32, 38), (10, 14), (19, 44), (31, 31), (17, 33), (53, 6), (48, 9), (6, 38), (30, 49), (52, 30), (7, 30), (45, 45), (21, 51), (7, 49), (11, 23))
      2 ((53, 6), (30, 49), (52, 30), (45, 45), (21, 51))
      3 >>> Pareto((1,2), (3,4), (2,2), (4,3), (7,0), (1,8))
      4 ((3, 4), (4, 3), (7, 0), (1, 8))
      5 
   

1. Написать функцию вычитания двух объектов

   • должно поддерживаться вычитание объектов, для которых вычитание уже определено (целые, вещественные, множества, ...)
   • должно поддерживаться вычитание упорядоченных хранимых последовательностей (кортежей, списков) по следующим правилам:
     • в "разность" должны попасть все элементы "уменьшаемого", которых нет в "вычитаемом"; если элемент встречается в "вычитаемом" хотя бы раз, то он не попадает в "разность"
     • элементы должны располагаться в "разности" в том же порядке, что и в "уменьшаемом"
   • Подсказки:
     • проверять на всех указанных выше типах последовательностей, для которых нужно реализовать вычитание

     • как работает type(object)()?

     • строка обрабатывается чуть-чуть не так, как кортеж (но есть вариант, когда так же)

      1 >>> SUB(123, 45)
      2 78
      3 >>> SUB((4,2,7,4,6,87,7), (2,54,67,3,2))
      4 (4, 7, 4, 6, 87, 7)
      5 >>> SUB(["Q", "WE", "RTY"], ["WE", "ZZ"])
      6 ['Q', 'RTY']
      7 >>> SUB({2,4,6,8}, {1,2,3,4})
      8 {8, 6}
      9 >>> SUB("qwretyqwerty", "qawsqas")
     10 'retyerty'
     11 
   

2. Реализовать рекурсивную функцию бинарного поиска (проверки наличия) элемента в упорядоченной по неубыванию индексируемой хранимой последовательности.

   • на вход подаётся искомый элемент и последовательность, гарантированно упорядоченная по неубыванию
   • бинарный поиск:

     • смотрим элемент в "середине" последовательности; если элемент равен искомому, то возвращаем TRUE; если элемент меньше искомого, ищем рекурсивно в "хвосте" последовательности; если элемент больше искомого, ищем рекурсивно в "голове" последовательности

     • при рекурсивном поиске, "хвост" и "голова" рассматриваются как новые последовательности

     • если искомый элемент не найден, возвращаем FALSE

     • если в последовательности чётное число элементов, "серединой" считается тот из двух средних элементов, у которого меньше индекс
     • проверить функцию на строках и кортежах

      1 >>> Bisect("a", "abcdfghklmoprsyz")
      2 True
      3 >>> Bisect("z", "abcdfghklmoprsyz")
      4 True
      5 >>> Bisect("l", "abcdfghklmoprsz")
      6 True
      7 >>> Bisect(6, (3,8,12,6,4,8,234,8,9)) # Это не должно работать! 
      8 False
      9 >>> Bisect(6, sorted((3,8,12,6,4,8,234,8,9))) # а это должно
     10 True
     11 >>> Bisect(6, (1,23,234,2354,25667))
     12 False
     13 >>> Bisect(6, range(2,17,2))
     14 True
     15 >>> Bisect(6, range(2,18,2))
     16 True
     17 >>> Bisect(6, range(3,18,2))
     18 False
     19 
   

3. Функционал-еval()-ище. Написать функцию calc(s, t ,u), которой передаются три строки. Каждая строка — это формула; s и t — над одной переменной x, а u — над двумя переменными x и y. Возвращается функция, которая по заданному x вычисляет u(s(x), t(x)).

   • Например, calc("x", "2*x+1", "x/y") должно возвращать функцию, которая вычисляет $$x / {2x+1}$$

        1 >>> F = Calc("x", "2*x+1", "x/y")
        2 >>> F(100)
        3 0.4975124378109453
        4 >>> F(0.1)
        5 0.08333333333333334
        6 >>> from math import *
        7 >>> F = Calc("sin(x)**2", "cos(x)**2", "x+y")
        8 >>> F(123)
        9 1.0
       10 >>> F(0.123)
       11 1.0
       12 >>> cos = lambda x: -x
       13 >>> sin = lambda x: x/2
       14 >>> F(123)
       15 18911.25
       16 >>> F = Calc("len(x)", "max(x)", "x+y")
       17 >>> F((1,2,34,56,12,3,1,7))
       18 64
       19