John Harrison - Введение в функциональное программирование (1108517), страница 23
Текст из файла (страница 23)
(*) Определите следующие функции:92Глава 7. Доказательство корректности программ7.5. Обращение списков#let rec sorted =fun [] -> true| [h] -> true| (h1::h2::t) -> h1 <= h2 & sorted(h2::t);;#let rec filter p =fun [] -> []| (h::t) -> let t’ = filter p t inif p h then h::t’ else t’;;#let sameprop p l1 l2 =length(filter p l1) = length(filter p l2);;#let rec permutes l1 l2 =fun [] -> true| (h::t) -> sameprop (fun x -> x = h) l1 l2 &permutes l1 l2 t;;#let permuted l1 l2 = permutes l1 l2 l1;;Определите назначение этих функций.
Реализуйте функцию сортировки sortи докажите, что для произвольных списков l справедливо, что sorted(sort l) =true and permuted l (sort l) = true.937.5. Обращение списковГлава 7. Доказательство корректности программ94Глава 8Эффективный MLВ этой главе мы обсудим некоторые техники и уловки, используя которые,ML программисты делают свои программы более элегантными и эффективными.Затем мы рассмотрим дополнительные императивные возможности, которыемогут быть задействованы, когда чистый функциональный подход представляетсянеподходящим.8.1Полезные комбинаторыГибкость функций высшего порядка означает, что можно написать небольшие,но весьма полезные функции, а затем многократно использовать для множествасходных задач. Такие функции часто называют комбинаторами, и не толькопотому, что они являются лямбда-термами без свободных переменных.
Эти функциизачастую оказываются настолько гибкими, что путём их совместной комбинацииможно реализовать практически всё что угодно.Например, очень полезный комбинатор для операций над списками, частоназываемый itlist или fold, выполняющий следующие действия:itlist f [x1 ; x2 ; . . . ; xn ] b = f x1 (f x2 (f x3 (· · · (f xn b))))Простое определение на ML:#let rec itlist f =fun [] b -> b| (h::t) b -> f h (itlist f t b);;itlist : (’a -> ’b -> ’b) -> ’a list -> ’b -> ’b = <fun>Довольно часто рекурсивные функции на списках заключаются просто вповторном применении некоторой функции к каждому элементу списка. Используяitlist с подходящим аргументом, такие функции можно очень легко реализоватьбез явного использования рекурсии.
Типичный пример – нахождение суммы всехчисел в списке.958.1. Полезные комбинаторыГлава 8. Эффективный ML#let sum l = itlist (fun x sum -> x + sum) l 0;;sum : int list -> int = <fun>#sum [1;2;3;4;5];;- : int = 15#sum [];;- : int = 0#sum [1;1;1;1];;- : int = 4Читатели, заинтересованные в краткости, могут предпочесть следующий код:#let sum l = itlist (prefix +) l 0;;Легко изменить эту функцию для вычисления произведения, вместо суммы.#let prod l = itlist (prefix *) l 1;;Многие полезные функции над списками могут быть реализованы подобнымобразом. Например, вот функция, которая отбирает только те элементы списка,которые удовлетворяют предикату:#let forall p l = itlistforall : (’a -> bool) ->#let exists p l = itlistexists : (’a -> bool) ->#forall (fun x -> x < 3)- : bool = true#forall (fun x -> x < 3)- : bool = false(fun h a -> p(h) & a) l true;;’a list -> bool = <fun>(fun h a -> p(h) or a) l false;;’a list -> bool = <fun>[1;2];;[1;2;3];;Эти функции проверяют наличие в списке элементов, удовлетворяющих предикату:#let forall p l = itlistforall : (’a -> bool) ->#let exists p l = itlistexists : (’a -> bool) ->#forall (fun x -> x < 3)- : bool = true#forall (fun x -> x < 3)- : bool = false(fun h a -> p(h) & a) l true;;’a list -> bool = <fun>(fun h a -> p(h) or a) l false;;’a list -> bool = <fun>[1;2];;[1;2;3];;А вот альтернативные версии length, append и map:.#let length l = itlist (fun x s -> s + 1) l 0;;length : ’a list -> int = <fun>#let append l m = itlist (fun h t -> h::t) l m;;append : ’a list -> ’a list -> ’a list = <fun>#let map f l = itlist (fun x s -> (f x)::s) l [];;map : (’a -> ’b) -> ’a list -> ’b list = <fun>Некоторые из этих функций сами по себе являются полезными комбинаторами.Например, если мы хотим рассматривать списки как множества, т.е.
исключаемкратные элементы, то многие стандартные операции на множествах очень простовыражаются в терминах только что рассмотренных комбинаторов:96Глава 8. Эффективный ML8.2. Создание эффективного кода#let mem x l = exists (fun y -> y = x) l;;mem : ’a -> ’a list -> bool = <fun>#let insert x l =if mem x l then l else x::l;;insert : ’a -> ’a list -> ’a list = <fun>#let union l1 l2 = itlist insert l1 l2;;union : ’a list -> ’a list -> ’a list = <fun>#let setify l = union l [];;setify : ’a list -> ’a list = <fun>#let Union l = itlist union l [];;Union : ’a list list -> ’a list = <fun>#let intersect l1 l2 = filter (fun x -> mem x l2) l1;;intersect : ’a list -> ’a list -> ’a list = <fun>#let subtract l1 l2 = filter (fun x -> not mem x l2) l1;;subtract : ’a list -> ’a list -> ’a list = <fun>#let subset l1 l2 = forall (fun t -> mem t l2) l1;;subset : ’a list -> ’a list -> bool = <fun>Функция setify предназначена для перевода списка в множество, посредствомисключения кратных элементов.8.2Создание эффективного кодаЗдесь мы собрали несколько общих приёмов, с помощью которых можно сделатьML программы существенно более эффективными.
Для того, чтобы оправдатьнекоторые из них, необходимо обрисовать в общих словах, как определённыеконструкции выполняются на «железе».8.2.1Хвостовая рекурсия и аккумуляторыОсновной механизм управления в функциональных программах – рекурсия. Еслимы заинтересованы в эффективных программах, нам следует подумать немного отом, как рекурсия реализуется на стандартном оборудовании.
В сущности, нет или,по крайней мере, мало отличий между реализацией ML и многими другими языкамис динамическими переменными, такими как С.В языках, не допускающих рекурсивных вызовов можно без опаски сохранять вселокальные переменные (включая и значения аргументов функции) в фиксированнойобласти памяти, так, например, сделано в FORTRAN.
Тем не менее, в общем случае,когда функция может вызываться рекурсивно, это не допустимо: вызов функции fс одним набором аргументов содержит вызов f, возможно, с другими аргументами.Это означает, что старые значения аргументов будут переписаны, даже если онимогут потребоваться в дальнейшем, после вызова вложенной f . Поясним сказанноена примере.
Рассмотрим ещё раз функцию факториала:#let rec fact n = if n = 0 then 1else n * fact(n - 1);;Вызов fact 6 приводит к последующему вызову fact 5 (и далее), но когда вызовfact 5 закончен, и получен результат, нам всё ещё требуется исходное значение n, аименно 6, для произведения, дающего окончательный ответ. Обычно в реализациях978.2. Создание эффективного кодаГлава 8. Эффективный MLпоступают следующим образом: для каждого вызова функции выделяется новыйстековый фрейм. И каждый новый вызов функции передвигает указатель стекадалее вниз 1 стека, выделяя пространство под новые переменные. В стековый фрейми копируются значения аргументов функции, её локальных переменных, иначе –состояние выполнения. После того, как вызванная функция завершает выполнение,указатель на стек перемещается обратно, таким образом, ненужные внутренниепеременные автоматически отбрасываются.
Схема может прояснить сказанное:n=6n=5n=4n=3n=2n=1SP-n=0Здесь изображён воображаемый снимок стека во время последнего рекурсивноговызова, т.е. вычисления fact 0. Все локальные переменные от предыдущих вызововсобраны в стеке, с каждым экземпляром функции, имеющим свой фрейм. Позавершению вызовов указатель стека SP перемещается обратно вверх.Следовательно, наша реализация fact требует n фреймов стека для вычисленияна аргументе n. Напротив, рассмотрим следующую реализацию функции,вычисляющей факториал:#let rec tfact x n =if n = 0 then xelse tfact (x * n) (n - 1);;tfact : int -> int -> int = <fun>#let fact n = tfact 1 n;;fact : int -> int = <fun>#fact 6;;- : int = 720Хотя tfact также рекурсивна, здесь рекурсивный вызов – итоговое выражение,после него никаких вычислений не происходит; оно не является подвыражением,частью другого выражения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
