close

Вход

Забыли?

вход по аккаунту

?

Презентация

код для вставкиСкачать
Сошников Дмитрий Валерьевич
к.ф.-м.н., доцент
dmitryso@microsoft.com
Факультет инноваций и высоких технологий
Московский физико-технический институт
Рекурсивные структуры
данных. Списки
2
©2008 Сошников Д.В.
Способ реализации итеративных вычислений
в функциональных языках - рекурсия
В традиционных языках
для итеративных
вычислений часто
используется
• Массив – область памяти
с произвольной
индексацией
• Список, стек, очередь...
В функциональных языках
для этих целей обычно
используют рекурсивные
структуры данных
• Списки
• Деревья
3
©2008 Сошников Д.В.
Список типа T (T list) – это
пустой список [] (или nil)
h::t
▪ элемент a:T (голова)
▪ список t:T list (хвост)
type 'a list =
| ([])
| (::) of 'a * 'a list
4
©2008 Сошников Д.В.
1::2::3::[] или [1;2;3]
“hello”::”there”::[] или [“hello”;”there”]
:: - это бинарный оператор,
синоним cons (constructor)
Все операции описаны в модуле
List, поэтому при их
использовании надо добавить в
программу open List, либо
указывать List.cons и т.д.
::
1
::
2
::
3
[]
5
©2008 Сошников Д.В.
Для отделения головы и хвоста обычно
используют pattern matching
let h::t = [1;2;3];;
match list with [] -> … | h::t -> …;;
Возможно также использовать функции hd
и tl (а также cons для создания)
6
©2008 Сошников Д.В.
Структура данных рекурсивна, потому что
она определяется через саму себя
Соответственно, для такой структуры хорошо
подходит рекурсивная обработка с pattern
matching
7
©2008 Сошников Д.В.
length : T list → int
• Встроенная функция модуля List
let rec length l =
match l with
[]
-> 0
| _::t -> 1+length(t)
;;
let rec length = function
[]
-> 0
| _::t -> 1+length(t);;
• length [1;2;3] → 1+length [2;3] → 1+1+length [3] →
1+1+1+length [] → 1+1+1+0 → 3
8
©2008 Сошников Д.В.
sum: int list → int
let rec sum = function
[x] -> x
| x::t -> x+sum t;;
•
•
let rec sum L =
match L with
[x] -> x
| x::t -> x+sum t;;
sum [1;2;3] → 1+sum [2;3] → 1+2+sum [3] → 1+2+3 → 6
В модуле List определены более общие функции
– sumByInt: (T→int) →T list →int
– sumByFloat: (T→float) →T list →float
•
let sum = sumByInt (fun x -> x);;
9
©2008 Сошников Д.В.
mem : T → T list → bool
•
Встроенная функция модуля List
let rec mem x = function
[] -> false
| z::t -> z=x or mem x t;;
•
•
mem 2 [1;2;3] → (1=2) or mem 2 [2;3] → mem 2 [2;3] → (2=2) or
mem 2 [3] → true
mem 4 [1;2] → (4=1) or mem 4 [2] → mem 4 [2] → (4=2) or mem 4 []
→ mem 4 [] → false
10
©2008 Сошников Д.В.
append: T list → T list → T list (встроенная)
let rec append M L =
match M with
[] -> L
| h::t -> h::(append t L);;
•
•
•
append [1;2] [3;4] → 1::append [2] [3;4] → 1::2::append [] [3;4] →
1::2::[3;4] = [1;2;3;4]
Определена как оператор @
[1;2] @ [3;4] → [1;2;3;4]
11
©2008 Сошников Д.В.
remove: T → T list → T list
let rec remove x = function
[] -> []
| h::t when h=x -> remove x t
| h::t -> h::remove x t;;
•
•
remove 3 [2;3;4;3] → if 3=2 then remove 3 [3;4;3] else 2::remove 3
[3;4;3] → 2::remove 3 [3;4;3] → 2::remove 3 [4;3] → 2::4::remove 3
[3] → 2::4::[] = [2;4]
Определите функцию для удаления только первого вхождения
элемента; для генерации списка всех возможных удалений
одного вхождения элемента
12
©2008 Сошников Д.В.
nth : A list -> int -> A – взятие n-го элемента
списка
concat : A list list -> A list – объединение
списка списков в один список
13
©2008 Сошников Д.В.
В духе функционального
программирования использовать принцип
функциональной абстракции
Например, удаление элемента может быть
обобщено до удаления элементов,
удовлетворяющих определенному условию
Сумма элементов списка – применение
некоторого действия ко всем элементам с
аккумулятором
14
©2008 Сошников Д.В.
• iter: (T → unit) → T list → unit
• iteri: (int→T→unit) → T list → unit
• iter2: (A→B→unit)→A list→B list
let rec iter f = function
[] -> ()
| h::t -> (f h); iter f t;;
•
Функции с суффиксами -i, -2 и -i2 доступны для многих библиотечных
функций
– -i - функции-обработчику передается номер элемента
– -2 – функция работает с двумя параллельными списками
•
•
List.iteri (fun n x -> printf "%d. %s\n" (n+1) x) ["One";"Two";"Three"];;
List.iter2 (fun n x -> printf "%d. %s\n" n x) [1;2;3] ["One";"Two";"Three"];;
15
©2008 Сошников Д.В.
find: (T → bool) → T list → T
если элемент не находится, то происходит исключение
tryfind: (T → bool) → T list → T option
find_index; find_indexi
tryfind_index; tryfind_indexi
type person = string*int;;
let plist = [("Vasya",123);("Petya",234)];;
let find_name no = List.tryfind
(fun (name,num) -> num=no) plist;;
match (find_name 123) with
None -> "No person found"
| Some((name,num)) -> "The person is "+name;;
16
©2008 Сошников Д.В.
map: (A → B) → A list → B list
let rec map f = function
[] -> []
| h::t -> (f h)::map f t;;
•
•
•
•
map (fun x->2*x) [1;2;3] = [2;4;6]
mapi (fun i x -> i*x) [1;2;3] = [0;2;6]
map (fun (s:string)->s.Length) ["One";"Two";"Three"] = [3;3;5]
["One";"Two";"Three"] |> map (fun s->s.Length)
17
©2008 Сошников Д.В.
filter: (T → bool) → T list → T list
let rec filter p = function
[] -> []
| x::t when p(x) -> x::filter p t
| x::t -> filter p t;;
• filter (fun x -> x%3=0) [1;2;3;4;5] = [3]
18
©2008 Сошников Д.В.
• fold_left: (В→А→В)→В→A list →B
– fold_left f s [a1;..;an] = f(..f(s,a1),a2,…),an)
• fold_right: (A→B→В)→A list→B→B
– fold_right f [a1;..;an] s = f(a1,f(…f(an,s))..)
• reduce_left/right: (A→A→A)→A list→A
– reduce_left f [a1;..;an] = f(..f(a1,a2),a3,…),an)
– reduce_right f [a1;..;an] = f(a1,f(…f(an-1,an))..)
•
•
•
•
let sum = fold (fun ac x -> ac+x) 0;;
let prod = fold (fun ac x -> ac*x) 1;;
let sumByInt f = fold (fun ac x ->ac*(f x)) 0;;
let sum = reduce (fun u v -> u+v);;
19
©2008 Сошников Д.В.
• exists: (T → bool) → T list → bool
• for_all: (T → bool) → T list → bool
let exists p = fold_left (fun a x -> a or x) false
let for_all p = fold_left (fun a x -> a and x) true
20
•
•
•
•
•
©2008 Сошников Д.В.
•
zip / unzip (zip3/unzip3) – объединить два (три)
списка в список пар (троек) и наоборот
assoc a L = snd (find (fun (u,v) -> u=a) L)
choose
sort / stable_sort – рассматриваем на семинаре
partition – разбиение на 2 списка в зависимости
от предиката
scan_left, scan_right – поэлементная обработка
списка (map) с аккумулятором
21
Документ
Категория
Презентации
Просмотров
2
Размер файла
3 416 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа