Программирование
<<  Функциональное программирование Функциональное программирование  >>
Функциональное программирование
Функциональное программирование
Лекция 12
Лекция 12
Определение
Определение
Описание
Описание
Обход дерева
Обход дерева
Пример обработки: map
Пример обработки: map
Пример дерева общего вида: структура директорий
Пример дерева общего вида: структура директорий
Чуть более сложный пример
Чуть более сложный пример
Двоичные деревья
Двоичные деревья
Взаимосвязь с дер
Взаимосвязь с дер
Сведение дерева общего вида к двоичному
Сведение дерева общего вида к двоичному
Применение двоичных деревьев
Применение двоичных деревьев
Описание двоичного дерева
Описание двоичного дерева
Обходы двоичного дерева
Обходы двоичного дерева
Процедура обхода
Процедура обхода
Отложенные вычисления
Отложенные вычисления
Обход с аккумулятором
Обход с аккумулятором

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

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

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

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

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

2 Лекция 12

Лекция 12

Деревья

2

3 Определение

Определение

Дерево общего вида типа T – это Элемент типа T с присоединенными к нему 0 и более деревьями типа T Формально – связанный граф без циклов

3

4 Описание

Описание

Лист – это терминальный элемент без поддеревьев Узел – это элемент, содержащий значение и поддеревья

type 'T tree = Leaf of 'T | Node of 'T*('T tree list);;

let tr = Node(1,[ Node(2,[ Leaf(5)]); Node(3,[ Leaf(6); Leaf(7)]); Leaf(4)]);;

4

5 Обход дерева

Обход дерева

Обход – это процедура, которая посещает каждый узел дерева один и только один раз

let rec iter f = function Leaf(T) -> f(T) | Node(T,L) -> (f(T); for t in L do iter f t done);; let iterh f = let rec itr n = function Leaf(T) -> f n T | Node(T,L) -> (f n T; for t in L do itr (n+1) t done) in itr 0;; let print_tree T = iterh (fun h x -> printf "%s%A\n" (spaces (h*3)) x) T;;

5

6 Пример обработки: map

Пример обработки: map

map: (A ? B) ? A tree ? B tree

print_tree (map (fun x->2*x) tr);; В качестве упражнения опишите другие преобразования деревьев – отрубание листьев, maph, зеркальное переворачивание и т.д.

let rec map f = function Leaf(T) -> Leaf(f T) | Node(T,L) -> Node(f T,List.map (fun t -> map f t) L);;

6

7 Пример дерева общего вида: структура директорий

Пример дерева общего вида: структура директорий

Дерево неявно порождается с помощью генератора на каждом уровне Возможный способ задания дерева! В качестве упражнения – построение структуры директорий в виде дерева в памяти в явном виде

#light open System.IO let rec tree path ind = Directory.GetDirectories path |> Array.iter(fun dir -> printfn "%s%s" (spaces (ind*3)) dir; tree dir (ind+1) );;

7

8 Чуть более сложный пример

Чуть более сложный пример

let rec du path = Directory.GetDirectories path |> Array.iter(fun dir -> let sz = Directory.GetFiles dir |> Array.map(fun f -> new FileInfo(f)) |> Array.fold_left (fun ac x -> ac+x.Length) 0L; printfn "%10d %s" sz dir; du dir );;

8

9 Двоичные деревья

Двоичные деревья

Двоичное дерево типа T – это Пустое дерево Nil Элемент типа T с двумя поддеревьями – левым и правым

9

10 Взаимосвязь с дер

Взаимосвязь с дер

общ.вида

Двоичные деревья – это не есть частный случай деревьев общего вида: Различие между левым и правым поддеревьями Двоичное дерево может быть пустым

10

11 Сведение дерева общего вида к двоичному

Сведение дерева общего вида к двоичному

Любое дерево общего вида может быть преобразовано к двоичному

11

12 Применение двоичных деревьев

Применение двоичных деревьев

Деревья поиска Способ представления упорядоченных данных в памяти с эффективными алгоритмами добавления/удаления элемента и поиском В неявном виде используются при определении структур данных типа ассоциативных таблиц, при индексировании и т.д. Деревья выражений Представление арифметических выражений с бинарными операторами

12

13 Описание двоичного дерева

Описание двоичного дерева

Лист – это терминальный элемент без поддеревьев Узел – это элемент, содержащий значение и поддеревья

type 't btree = Node of 't * 't btree * 't btree | Nil ;;

let tr = Node(6, Node(3, Node(1,Nil,Nil), Node(4,Nil,Nil)), Node(7,Nil,Nil));;

13

14 Обходы двоичного дерева

Обходы двоичного дерева

КЛП, прямой, префиксный [+ * 1 2 3] ЛКП, обратный, инфиксный [1*2+3] ЛПК, концевой, постфиксный [1 2 * 3 +] + 3 симметричных

14

15 Процедура обхода

Процедура обхода

let prefix root left right = (root(); left(); right());; let infix root left right = (left(); root(); right());; let postfix root left right = (left(); right(); root());; let iterh trav f t = let rec tr t h = match t with Node (x,L,R) -> trav (fun () -> (f x h)) (fun () -> tr L (h+1)) (fun () -> tr R (h+1)); | Nil -> () in tr t 0;; let print_tree T = iterh infix (fun x h -> printf "%s%A\n" (spaces h) x) T;;

15

16 Отложенные вычисления

Отложенные вычисления

prefix/infix/postfix: Переключатели типа обхода (unit?unit)? (unit?unit)? (unit?unit)?unit unit?unit – это функциональный тип fun () -> … - создает функцию такого типа () – вызов этой функции

16

17 Обход с аккумулятором

Обход с аккумулятором

Производит инфиксный обход дерева Вычисляет f(a1,f(a2,…,f(an,init))..) Дерево в список:

let fold_infix init f t = let rec tr t x = match t with Node (z,L,R) -> tr R (f z (tr L x)) | Nil -> x in tr t init;;

let tree_to_list T = fold_infix [] (fun x l -> x::l) T;;

17

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

Программирование

31 презентация о программировании
Урок

Информатика

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