Программирование
<<  Разработка приложений на платформе Функциональное программирование  >>
Функциональное программирование
Функциональное программирование
Лекция 13
Лекция 13
Дерево поиска
Дерево поиска
Вставка элемента в дерево поиска
Вставка элемента в дерево поиска
Эффективность поиска
Эффективность поиска
Сортировка списка
Сортировка списка
Деревья выражений
Деревья выражений
Вычисление выражения
Вычисление выражения
Разбор выражения в дерево
Разбор выражения в дерево
Префиксная форма
Префиксная форма
Другие алгоритмы
Другие алгоритмы
Хвостовая рекурсия для деревьев
Хвостовая рекурсия для деревьев
Определение размера дерева
Определение размера дерева
Улучшенный вариант
Улучшенный вариант
Мораль
Мораль
Вопросы
Вопросы

Презентация на тему: «Функциональное программирование». Автор: Митя;Dmitry Soshnikov. Файл: «Функциональное программирование.ppt». Размер zip-архива: 2790 КБ.

Функциональное программирование

содержание презентации «Функциональное программирование.ppt»
СлайдТекст
1 Функциональное программирование

Функциональное программирование

Факультет инноваций и высоких технологий Московский физико-технический институт

2 Лекция 13

Лекция 13

Деревья выражений и деревья поиска. Продолжения

2

3 Дерево поиска

Дерево поиска

Дерево поиска типа T, на котором определен полный порядок < - это двоичное дерево, для каждой вершины x которого

Все вершины левого поддерева меньше х Все вершины правого поддерева больше х

3

4 Вставка элемента в дерево поиска

Вставка элемента в дерево поиска

Повторно элемент не вставляется (возвращается исходное дерево) Проход по дереву от корня до листьев, всегда добавляется лист Сложность – O(h) Дерево поиска по списку элементов:

let rec insert x t = match t with Nil -> Node(x,Nil,Nil) | Node(z,L,R) -> if z=x then t else if x<z then Node(z,insert x L,R) else Node(z,L,insert x R);;

let list_to_tree L = List.fold_left (fun t x -> insert x t) Nil L;;

4

5 Эффективность поиска

Эффективность поиска

Эффективность поиска зависит от конфигурации дерева поиска: Худший вариант: O(n), list_to_tree [1;2;3;4];; линейный поиск Лучший вариант: O(log2n) сбалансированное дерево двоичный поиск Древовидные алгоритмы поиска находятся посередине между двоичным и линейным поиском по эффективности поиска, но в них проще реализуется вставка элементов

5

6 Сортировка списка

Сортировка списка

Указание «правильного» определения: let tree_sort = list_to_tree >> tree_to_list;; на F# приводит к проблеме с выводом типов, называемой value restriction – для неявных аргументов компилятор не производит обобщение типов, и не может правильно определить generic type. Решение: в явном виде указать тип, или указать явный аргумент.

let tree_sort : int list -> int list = list_to_tree >> tree_to_list;; let tree_sort L = (list_to_tree >> tree_to_list) L;;

6

7 Деревья выражений

Деревья выражений

Арифметические выражения с бинарными и унарными операциями удобно представлять двоичными деревьями Можно использовать описанный ранее тип, или ввести более «прозрачный»

Здесь операция представляется char, но более правильно конечно использовать discriminated union (Enum)

type ExprTree = Op of char*ExprTree*ExprTree | Value of int;; let sample = Op('+',Op('*', Value(1),Value(2)),Value(3));;

7

8 Вычисление выражения

Вычисление выражения

Рекурсивный обход дерева, для каждого узла – вычисление операции для левого и правого поддерева

let rec compute = function Value(x) -> x | Op(op,L,R) -> match op with '+' -> compute L+compute R | '-' -> compute L-compute R | '*' -> compute L*compute R | '/' -> compute L/compute R;;

8

9 Разбор выражения в дерево

Разбор выражения в дерево

Простейший алгоритм грамматического разбора Метод рекурсивного спуска: система взаимно рекурсивных функций; каждая функция разбирает свой фрагмент дерева Функция разбора воспринимает входной поток символов, потребляет столько символов, сколько ей нужно Используется подход с разностными списками: функция принимает на вход список символов, возвращает пару: остаток списка и дерево выражения

9

10 Префиксная форма

Префиксная форма

parse_infix ['+';'*';'1';'2';'3']= Op ('+',Op ('*',Value 1,Value 2),Value 3)

let parse_infix expr = let rec ff expr = match expr with [] -> failwith "Error" | h::t when System.Char.IsDigit(h) -> (t,Value(System.Int32.Parse(h.ToString()))) | h::t when h=' ' -> ff t | h::t -> let (t1,l) = ff t in let (t2,r) = ff t1 in (t2,Op(h,l,r)) in snd (ff expr);;

10

11 Другие алгоритмы

Другие алгоритмы

Разбор выражения в префиксной/инфиксной/постфиксной форме в дерево Замена переменной на подвыражение (для этого расширить тип, добавив Var of char) Вычисление выражения в постфиксной форме (с деревом и без) Вычисление выражение в инфиксной форме без использования дерева

11

12 Хвостовая рекурсия для деревьев

Хвостовая рекурсия для деревьев

На первый взгляд хвостовая рекурсия для деревьев невозможна нелинейная рекурсия не может быть сведена к итерации В императивных языках рекурсия сводится к итерации с помощью стека В стеке запоминаются «адреса возврата» и параметры В функциональном программировании можно использовать continuations (продолжения)

12

13 Определение размера дерева

Определение размера дерева

let size t = let rec size' t cont = match t with Nil -> cont 0 | Node(_,L,R) -> size' L (fun x1 -> size' R (fun x2 -> cont(x1+x2+1))) in size' t (fun x->x);;

let rec size t = Nil -> 0 | Node(_,L,R) -> 1+size L+size R;;

Continuation – это явно передаваемая функция, указывающая, какие вычисления проводить после применения рекурсии Вместо рекурсивного вызова мы строим функцию, содержащую рекурсивный вызов Функции строятся не на стеке, а в куче (heap) -> избегаем переполнения стека Рекурсия действительно получается хвостовая! Дерево развертывается в последовательные вызовы функции

13

14 Улучшенный вариант

Улучшенный вариант

Используется сочетание аккумулятора с продолжением Аналогично использованию стека с циклом

let size t = let rec size' acc t cont = match t with Nil -> cont acc | Node(_,L,R) -> size' (1+acc) L (fun x -> size' x R cont) in size' 0 t (fun x->x);;

14

15 Мораль

Мораль

Деревья не имеют непосредственной поддержки в библиотеке языка Часто реализуются программистом с учетом особенностей задачи Два часто используемых варианта использования двоичных деревьев Деревья поиска Деревья выражений Деревья общего вида Файлы и директории Процессы, нити, ... Типы данных, основанные на деревьях …

15

16 Вопросы

Вопросы

16

«Функциональное программирование»
http://900igr.net/prezentacija/informatika/funktsionalnoe-programmirovanie-91343.html
cсылка на страницу
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Программирование > Функциональное программирование