Сошников Дмитрий Валерьевич к.ф.-м.н., доцент Факультет инноваций и высоких технологий Московский физико-технический институт

2 Лекция 8 Рекурсивные структуры данных. Списки

©2008 Сошников Д.В. 3 Способ реализации итеративных вычислений в функциональных языках - рекурсия В традиционных языках для итеративных вычислений часто используется Массив – область памяти с произвольной индексацией Список, стек, очередь... В функциональных языках для этих целей обычно используют рекурсивные структуры данных Списки Деревья

©2008 Сошников Д.В. 4 Список типа T (T list) – это пустой список [] (или nil) h::t элемент a:T (голова) список t:T list (хвост) type 'a list = | ([]) | (::) of 'a * 'a list

©2008 Сошников Д.В. 5 1::2::3::[] или [1;2;3] hello::there::[] или [hello;there] :: - это бинарный оператор, синоним cons (constructor) Все операции описаны в модуле List, поэтому при их использовании надо добавить в программу open List, либо указывать List.cons и т.д [] ::

©2008 Сошников Д.В. 6 Для отделения головы и хвоста обычно используют pattern matching let h::t = [1;2;3];; match list with [] -> … | h::t -> …;; Возможно также использовать функции hd и tl (а также cons для создания)

©2008 Сошников Д.В. 7 Структура данных рекурсивна, потому что она определяется через саму себя Соответственно, для такой структуры хорошо подходит рекурсивная обработка с pattern matching

©2008 Сошников Д.В. 8 length : T list int length [1;2;3] 1+length [2;3] 1+1+length [3] length [] let rec length l = match l with [] -> 0 | _::t -> 1+length(t) ;; let rec length = function [] -> 0 | _::t -> 1+length(t);; Встроенная функция модуля List

©2008 Сошников Д.В. 9 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] В модуле List определены более общие функции –sumByInt: (Tint) T list int –sumByFloat: (Tfloat) T list float let sum = sumByInt (fun x -> x);;

©2008 Сошников Д.В. 10 Встроенная функция модуля 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 mem : T T list bool

©2008 Сошников Д.В. 11 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] Определена как [3;4] [1;2;3;4]

©2008 Сошников Д.В. 12 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] Определите функцию для удаления только первого вхождения элемента; для генерации списка всех возможных удалений одного вхождения элемента

©2008 Сошников Д.В. 13 nth : A list -> int -> A – взятие n-го элемента списка concat : A list list -> A list – объединение списка списков в один список

©2008 Сошников Д.В. 14 В духе функционального программирования использовать принцип функциональной абстракции Например, удаление элемента может быть обобщено до удаления элементов, удовлетворяющих определенному условию Сумма элементов списка – применение некоторого действия ко всем элементам с аккумулятором

©2008 Сошников Д.В. 15 iter: (T unit) T list unit iteri: (int T unit) T list unit iter2: (A B unit) A list B list 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"];;

©2008 Сошников Д.В. 16 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;; find: (T bool) T list T если элемент не находится, то происходит исключение tryfind: (T bool) T list T option find: (T bool) T list T если элемент не находится, то происходит исключение tryfind: (T bool) T list T option

©2008 Сошников Д.В. 17 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)

©2008 Сошников Д.В. 18 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]

©2008 Сошников Д.В. 19 fold_left: (В А В) В A list B –fold_left f s [a 1 ;..;a n ] = f(..f(s,a 1 ),a 2,…),a n ) fold_right: (A B В) A list B B –fold_right f [a 1 ;..;a n ] s = f(a 1,f(…f(a n,s))..) reduce_left/right: (A A A) A list A –reduce_left f [a 1 ;..;a n ] = f(..f(a 1,a 2 ),a 3,…),a n ) –reduce_right f [a 1 ;..;a n ] = f(a 1,f(…f(a n-1,a n ))..) fold_left: (В А В) В A list B –fold_left f s [a 1 ;..;a n ] = f(..f(s,a 1 ),a 2,…),a n ) fold_right: (A B В) A list B B –fold_right f [a 1 ;..;a n ] s = f(a 1,f(…f(a n,s))..) reduce_left/right: (A A A) A list A –reduce_left f [a 1 ;..;a n ] = f(..f(a 1,a 2 ),a 3,…),a n ) –reduce_right f [a 1 ;..;a n ] = f(a 1,f(…f(a n-1,a n ))..) 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);;

©2008 Сошников Д.В. 20 exists: (T bool) T list bool for_all: (T bool) T list bool 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

©2008 Сошников Д.В. 21 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) с аккумулятором 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) с аккумулятором