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

sorted() и max()/min() там, где функции

Функции

Пространства имён: повторение

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

• Задание функции: формальные и фактические параметры, return

• Duck typing: функция как формализация алгоритма

• вызов функции как локальное пространство имён

  • globals() и locals()

  • сложный случай определение локальности по связыванию, global

  • nonlocal для вложенных вызовов

• функция как объект: именование, передача в качестве параметра
• Распаковка и запаковка параметров
  • функция с произвольным числом параметров
• Параметры функции по умолчанию (именованные параметры)

  • (to be continued… они теперь не равны, вообще см. полный вид описания функции)

Про рекурсию

• Рекурсия и цикл. Теория vs. практика. Гвидо, Python и хвостовой вызов

  • ⇒ максимальная глубина рекурсии
  • ⇒ логарифмический критерий уместности рекурсии

• Замещение рекурсии стеком. Пример: есть ли среди натуральных чисел Seq такие, что в сумме дают S. Рекурсивный вариант.

  •    1 def subsumR(S, Seq, Res=[]):
       2     if sum(Res) == S:
       3         return Res
       4     for i, el in enumerate(Seq):
       5         R = subsumR(S, Seq[i+1:], Res+[el])
       6         if R: return R
       7     return []
    

    S — неизменяемая часть, Seq, Res — изменяемая, значит, их надо сохранять в стек. Рекурсия — это цикл, которые продолжается до тех пор, пока рекурсивные вызовы не кончились.

       1 def subsumS(S, Num):
       2     Stack = [(Num,[])]
       3     while Stack:
       4         Seq, Res = Stack.pop()
       5         if sum(Res) == S:
       6             return Res
       7         Stack.extend([(Seq[i+1:], Res+[el]) for i, el in enumerate(Seq)])
       8     return []
    

    • здесь не тот порядок добавления, для полного соответствия надо в обратном
    • вместо списковой сборки надо использовать генератор, но у нас их ещё не было ☺

Замыкание

Замыкание_(программирование)

1. Функция — это объект
2. Её можно изготовить внутри другой функции и вернуть
3. …причём в зависимости от параметров этой другой функции!
4. …в процессе чего некоторые объекты из ПИ создающей функции «залипают» в ПИ создаваемой
   • только они там навсегда должны залипнуть, а не только на время вызова

   • ⇒ .__closure__

5. Это и есть замыкание!

Пример:

   1 def f1(x):
   2     def f2():
   3         return x
   4     return f2

pythontutor this

и

   1 def f1(x):
   2     def f2():
   3         def f3():
   4             return x
   5         return f3
   6     return f2

pythontutor this

Also: nonlocal name — явное указание брать имя name из внешнего, но не глобального пространства имён

Примеры: 1 и 2

Замыкание и позднее связывание

Вот этот код не работает так, как может показаться:

   1 def create_adders():
   2     adders = []
   3     for i in range(10):
   4         def adder(x):
   5             return i + x
   6         adders.append(adder)
   7     return adders
   8 
   9 for adder in create_adders():
  10     print(adder(1))

Обратите внимание на то, что все adder-ы работают одинаково!. Поскольку i для сгенерированных функций нелокальное, оно попадает в замыкание, и это один и тот же объект во всех adder-ах:

>>> c = create_adders()
>>> c[1]
<function create_adders.<locals>.adder at 0x7f272d2f93b0>
>>> c[1].__closure__
(<cell at 0x7f272d1c1510: int object at 0x7f272db36660>,)
>>> c[2].__closure__
(<cell at 0x7f272d1c1510: int object at 0x7f272db36660>,)
>>> c[2].__closure__[0].cell_contents
9
>>> c[1].__closure__[0].cell_contents
9

Если мы хотели не этого, надо сделать так, чтобы при создании очередного adder-а его i именовало новый объект:

   1 def create_adders():
   2     adders = []
   3     for i in range(10):
   4         def adder(x, j=i):
   5             return j + x
   6         adders.append(adder)
   7     return adders

При этом никакого замыкания не произойдёт, у каждого adder-а будет своё локальное j, инициализированное соответствующим значением i. (Если бы нам нужно было сильнее запутаться, мы могли бы написать i=i вместо j=i ☺ ).

   1 >>> c = create_adders()
   2 >>> c[1].__closure__
   3 >>> print(c[1].__closure__)
   4 None

Д/З

0. Прочитать:

   • в Tutorial про функции

   • Про замыкания: Gabor Laszlo Hajba и Dmitry Soshnikov

   • Посмотреть, как оформлять задачи типа «написать функцию», Три задачи этого Д/З имеют такой новый тип.

1. EJudge: DivDigit 'Цифроделители'

   Написать функцию divdigit(N), которой передаётся произвольное натуральное число N, а в ответ функция возвращает количество цифр этого числа, являющихся её делителями.

   Input:

   print(divdigit(312345))

   Output:

   4

2. EJudge: BinPow 'Бинарное возведение в степень'

   Написать функцию BinPow(), которая принимает три параметра: python3-объект a, натуральное число 0<N<1000000, и некоторую ассоциативную бинарную функцию f(). Функция BinPow() реализует алгоритм бинарного возведения в степень (кроме нулевой степени). Результатом BinPow(a, n, f) будет применение f(x) к a n-1 раз.

   Input:

      1 print(BinPow(2,33, int.__mul__), 2**33)
      2 print(BinPow("Se", 7, str.__add__))
   

   Output:

   8589934592 8589934592
   SeSeSeSeSeSeSe

3. EJudge: Det4x4 'Определитель матрицы 4×4'

   Матрица 4×4 задаётся кортежем из 4 кортежей по 4 целых числа в каждом. Посчитать точный определитель этой матрицы. Пользоваться itertools нельзя.

   Input:

   (5, -4, 4, -7), (1, -2, 6, 0), (3, -8, -6, -4), (-1, 2, -9, 3)

   Output:

   702

4. EJudge: FunVect 'Вектор функций'

   Написать функцию superposition(funmod, funseq), которая принимает два параметра — функцию funmod() от одного переменного, и последовательность funseq[] функций от одного переменного. superposition() возвращает также список функций funres[], каждая из которых представляет собой суперпозицию вида funres[i] ::== funmod(funseq[i])

   Input:

      1 from math import *
      2 F = superposition(abs, (sin, cos))
      3 print(F[0](-1), F[1](-1), F[0](2), F[1](2))
   

   Output:

   0.8414709848078965 0.5403023058681398 0.9092974268256817 0.4161468365471424