1 Д.з. 1+1/(1+1/(1+…)) f n = 1+1/(1+1/(1+…)) f (n-1) f 0 = 1 f n = 1 + 1/f (n-1) 2 φ = 1.618… - презентация

1 1 Д.з.

2 1+1/(1+1/(1+…)) f n = 1+1/(1+1/(1+…)) f (n-1) f 0 = 1 f n = 1 + 1/f (n-1) 2 φ = 1.618…

3 Золотое сечение 3 Такой предмет у вас в сумке?

4 0+1/(1+1/(2+1/3+…)) b n = 0+1/(1+1/(2+1/3+…)) При трудностях помогает доп.параметр b k n = k+1/(k+1+1/(...+1/n))) b n = b' 0 n b' k n = if (k == n) then n else k + 1 / b' (k+1) n 4

5 5 sumsin sin( n)/(sin 1+sin sin n) Накапливающие параметры s1 s2 0 1 sin sin 1 + sin sin 1 + sin 2 + sin 3 … sumsin n = sumsin' n 0 0 sumsin' 0 s1 s2 = sin s1 / s2 sumsin' n s1 s2 = sumsin' (n-1) (s1+n) (s2+sin n)

6 6 sumfact 1!+2!+3!+…+n! Желательно O(n) i ps *2 1+1*2 4 1*2*3 1+1*2+1*2*3 5 1*2*3*4 1+1*2+1*2*3+1*2*3*4 sumfact n = sumfact' n sumfact' 0 i p s = s sumfact' n i p s = sumfact' (n-1) (i+1) (p*i) (s+p*i)

7 7 Безымянная переменная (wildcard) sumfact' 0 i p s = s Лучше так: sumfact' 0 _ _ s = s _ - безымянная переменная (wildcard) Только слева от =

8 8 let sumfact' n i p s = sumfact' (n-1) (i+1) (p*i) (s+p*i) Еще одна проблема (небольшая в данном случае) p*i – два раза DRY (Dont Repeat Yourself) sumfact' n i p s = let p1 = p*i in sumfact' (n-1) (i+1) p1 (s+p1)

9 9 let в общем случае Двумерный синтаксис let правило1 правило2 … in выражение М.б. частью выражения f n = 1 + let i = 55 j = n*n + 5* n + 8 g k = k * j in g n * 2 Где кончается правило и начинается следующее? Двумерный синтаксис (off- side rule) Запоминаем позицию первой лексемы после let (i в примере) Правее продолжение правила На том же уровне новое правило Левее конец конструкции

10 10 Явное задание синтаксиса let правило1 правило2 … in выражение Можно использовать { ; }, тогда отступы не имеют значение let {правило1; правило2; правило3} in выражение

11 where sumfact' n i p s = sumfact' (n-1) (i+1) p1 (s+p1) where p1 = p*i левая часть = правая часть where вспомогательные определения Разница: let можно писать где угодно where – часть правила Тоже двумерный синтаксис 11

12 Забыл сказать Можно определять свои операторы i j = i*i + j*j Пример вызова 5 7 Может использоваться любая последовательность символов (кроме зарезервированных типа -> и ::) Обычные функции можно использовать, как инфиксный оператор Надо взять в обратные кавычки (`) i `mod`

13 Refential transparency Что такое побочный эффект? Прозрачность по ссылкам (referential transparency) … f 5 + … f 5 … Вызовы с одинаковыми параметрами всегда дают одинаковые значения Можно заменить на один вызов (с помощью let, например) Не очень понятно: А как же случайные числа?? А как же ввод/вывод?? 13

14 Списки 14

15 Списки Основной тип данных (и почти во всех функциональных языках) Примеры: [1, 2, 3] [3.5, 2.123, 98.14] [True, False] Элементы д.б. одного типа! [1, True, 2] -- Ошибка! 15

16 Как создавать списки Оператор : Оператор : Приписать элемент в начало 1 : [2,3] [1,2,3] Пример: f 0 = [] f n = n : f (n-1) Список чисел от n до 1 Кстати: [a..b] – числа от a до b с шагом 1 На самом деле, [1,2,3] – это просто сокращение! [1, 2, 3] – сокращение для 1:2:3:[] Так и хранится: : / \ 1 : / \ 2 : / \ 3 [] 16

17 Как обрабатывать списки – способ 1 head – первый элемент списка tail – все, кроме первого элемента («хвост») head [1,2,3] 1 tail [1,2,3] [2,3] 17 Пример: сумма элементов списка sum [] = 0 sum xs = head xs + sum(tail xs) Замечания: Типичные имена для списков в Haskel: xs, ys и т.д. sum – на самом деле, есть такая стандартная фунцкия

18 Шаблоны Как обрабатывать списки – способ 2 sum [] = 0 sum (x:xs) = x + sum xs Слева от = м.б. выражение с переменными – шаблон (pattern) Шаблоны м.б. довольно сложным Примеры: f [x, y, z] f [1, y, 2] f (x:y:xs) f (x:1:xs) Замечания: sum (x:xs) – скобки нужны! Еще раз, правило линейности: f [x, y, x] -- ошибка! 18

19 Еще пример product – произведение чисел списка (стандартная функция) product [] = 1 product (x:xs) = x * product xs Снова факториал fact n = product [1..n] Это стиль Haskell! Fritz Rueh The Evolution of a Haskell Programmer uehr/haskell/evolution.html uehr/haskell/evolution.html 19

20 ++ Еще одна стандартная функция Конкатенация [1,2] ++ [3,4] [1,2,3,4] [] ++ ys = ys (x:xs) ++ ys = x : (xs ++ ys) Кстати: как приписывать в конец списка xs : x Нет! : приписывает только в начало! xs ++ x Нет! ++ работает только со списками! xs ++ [x] OK Но O(n) – медленно! 20

21 Функции высшего порядка 21

22 Пример: map Взять синус от всех элементов списка sinAll [] = [] sinAll (x:xs) = sin x : sinAll xs Взять косинус от всех элементов списка cosAll [] = [] cosAll (x:xs) = cos x : cosAll xs Возвести все элементы списка в квадрат DRY :( Надо что-то делать! map map f [] = [] map f (x:xs) = f x : map f xs Примеры вызова map sin [1,2,3] [sin 1, sin 2, sin 3] map sqr [1,2,3] [1,4,9] Функция высшего порядка! 22

23 Лямбда-выражения Почему в обычных языках (Паскаль, C) этим мало пользуются? Еще задача: Каждое число в списке умножить на 10 и прибавить 5. f x = 10 * x + 5 map f xs Надо описывать вспомогательные функции – лень Надо придумывать имена – тоже лень Лямбда-выражение – функция без имени \i -> 10*x + 5 map (\i -> 10*i+5) xs Синтаксис: \ параметр1 параметр2 -> выражение \ - то, что осталось от λ Ограничения: М.б. только одно правило (но case) Естественно, не м.б. рекурсивно 23

24 А также.. Еще мы прошли: Решение задачи про разложение на слагаемые Пары и наборы (tuples) и работу с ними Слайды на эту тему будут в следующей презентации, заодно вкратце еще раз все это повторим 24

25 Д.з. 25

26 Д.з Описать функцию minlist, которая ищет минимальный элемент в данном списке. 2. Описать функцию minsum, которая ищет минимум суммы двух стоящих рядом элементов в данном списке. minsum [1,8,3,2,7] Ответ должен быть равен 5 (3+2) 3. Описать фунццию rev, которая для списка возвращает список из тех же элементов, но идуших в обратном порядке. rev [1, 3, 7] [7, 3, 1] O(n), если получится 26

27 Д.з Описать функцию check cond xs, верно ли, что есть элемент, для которого выполняется cond Примеры вызова: check (\x->x>5) [3,2,7,4] True check (\x->x>10) [3,2,7,4] False 5. Описать функцию checkDifferent, которая возвращает True, если все элементы в списке разные Примеры вызова: checkDifferent [3,2,7] True. checkDifferent [3,2,7,5,7,8] False 27