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

2 Лекция 6 Сопоставление с образцом. Рекурсия. Циклы

©2008 Сошников Д.В. 3 type document = SSN of int | Passport of string;; type personx = string * int * document;; let vasyax = ("Vasya",14,SSN 1234);; let (_,_,doc)= vasyax;; match vasyax with _,_,SSN x -> print_int x | _,_,Passport s -> print_string s ;; let print_doc = function _,_,SSN x -> print_int x | _,_,Passport s -> print_string s in print_doc vasyax;;

©2008 Сошников Д.В. 4 match expr with pattern1 [when cond1] -> expr1 | pattern2 [when cond2] -> expr1 | … ;; match D with _ when D>0 -> Два корня | _ when D=0 -> Один корень | _ -> Нет корней ;; match root with Some(t) -> printf Корень: %d\n t | None -> printf Корней нет\n

©2008 Сошников Д.В. 5 Конструкции для определения лямбда- выражений: fun Поддерживает несколько аргументов в каррированной форме: fun x y -> … Не поддерживает pattern matching function Поддерживает только один аргумент (возможно, tuple) Поддерживает pattern matching с несколькими вариантами описания

©2008 Сошников Д.В. 6 let rec fact1 = function 1 -> 1 | x -> x*fact1(x-1);; let rec fact2 x = match x with 1 -> 1 | x -> x*fact2(x-1);; // это уже не pattern matching let rec fact3 x = if x = 1 then 1 else x * fact3(x-1);;

©2008 Сошников Д.В. 7 Определения в F# могут быть рекурсивными, т.е. в рамках «let rec»- определения возможно использовать определяемую функцию В λ-исчислении напрямую понятия рекурсии нет – мы позднее узнаем, как определяется рекурсия в λ-исчислении Рекурсия – зачастую единственный способ совершения итеративных действий

©2008 Сошников Д.В. 8 let rec print_n a b = if a>=b then print_int b else begin print_int a; print_n (a+1) b end;; print_n 1 10;; Напечатать числа от a до b

©2008 Сошников Д.В. 9 Группировка по блокам регулируется отступами Можно опускать некоторые элементы синтаксиса, например, in в let … in … #light let rec print_n a b = if a>=b then print_int b else print_int a print_n (a+1) b ;; print_n 1 10;;

©2008 Сошников Д.В. 10 print_n – типичная реализация цикла со счетчиком Необходимо выполнить какое-то действие несколько раз, при этом переменная- счетчик меняется от a до b Действие можно задать функцией int unit Функционал – функция, принимающая или возвращающая функцию

©2008 Сошников Д.В. 11 В F# (но не в других функц.языках) имеется также встроенная конструкция цикла for: let rec forl a b f = if a>=b then f b else f a forl (a+1) b f ;; forl 1 10 (fun i -> print_int i);; for i=1 to 10 do print_int i;; for i in do print_int i;;

©2008 Сошников Д.В. 12 fora a b i f = f(f(…f(i,b),…),a+1,a) let rec fora a b i f = if a>=b then i else f (fora (a+1) b i f) a ;; fora 1 10 (fun a i -> a+i);; Посчитаем сумму чисел от 1 до 10: А сумму x^n/n!

©2008 Сошников Д.В. 13 (* Следующее за 10 простое число *) whilel 10 (fun i -> not is_prime i);; (* sin(sin(sin(x))) *) let sin3 x = reccall 3 sin x;; let sin3 = reccall 3 sin;;

©2008 Сошников Д.В. 14 Линейная Вызов функции генерирует не более одного рекурсивного вызова Нелинейная (плохая) let rec fib a = if a

©2008 Сошников Д.В. 15 Прямая Косвенная A вызывает B; B вызывает C; С вызывает A Часто встречается при построении компиляторов методом рекурсивного спуска let rec A = … B … and B = … C … and C = … A …;;