1 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования Ленивые вычисления Рассмотрим выражение, содержащее операцию дизъюнкции (ИЛИ): (x == 0) || (y `div` x > 2) Опасно ли его вычислять при x == 0 ? Безопасное вычисление – дизъюнкция "по МакКарти" (McCarthy): if x == 0 then True else y `div` x > 2 (|||) :: Bool -> Bool -> Bool a ||| b = if a then True else b Безопасно ли выражение: (x == 0) ||| (y `div` x > 2) Способы передачи аргументов в функцию: «по значению» – значение аргумента вычисляется и передается в функцию; «по ссылке» – аргумент – это переменная, имя которой передается в функцию; «по наименованию» – значение аргумента вычисляется при каждом обращении к нему в теле функции; «по необходимости» – значение аргумента вычисляется при первом обращении к нему в теле функции.
2 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Энергичные и ленивые вычисления Энергичные вычисления: аргументы всех функций вычисляются до момента входа в функцию; если аргумент не может быть вычислен, то значение функции не определено (все функции – строгие по всем своим аргументам). Ленивые вычисления: аргументы функций не вычисляются до момента входа в функцию; вычисление значения аргумента происходит при первом обращении к аргументу – когда его значение нужно для выполнения примитивной функции или в момент сопоставления с образцом; если функция не обращается к аргументу, то его значение не вычисляется. В языке Haskell все функции и конструкторы – нестрогие (ленивые) за исключением примитивных арифметических и логических операций. Выражения: (x == 0) || (y `div` x > 2) (x == 0) ||| (y `div` x > 2) «безопасны», так как и встроенная операция (||), и определенная программистом операция (|||) – ленивые.
3 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. «Бесконечные» списки Необычная функция: listFrom :: Integer -> [Integer] listFrom n = n : (listFrom (n+1)) listFrom 2 2 : (listFrom 3) 2 : (3 : (listFrom 4))... В случае «ленивых» конструкторов аргумент может понадобиться в момент сопоставления с образцом: sumFirst :: Integer -> [Integer] -> Integer sumFirst 0 _ = 0 sumFirst n (e:ls) = e + sumFirst (n-1) ls sumFirst 3 (listFrom 2) sumFirst 3 (2 : (listFrom 3)) 2 + sumFirst 2 (listFrom 3) 2 + sumFirst 2 (3 : (listFrom 4)) 2 + (3 + sumFirst 1 (listFrom 4)) 2 + (3 + sumFirst 1 (4 : (listFrom 5))) 2 + (3 + (4 + sumFirst 0 (listFrom 5))) 2 + (3 + (4 + 0)) 9
4 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Значения и функции, приводящие к образованию «бесконечных» списков [2..] [3, 6..] [x*x | x [a] repeat e = ls where ls = e : ls cycle :: [a] -> [a] cycle ls = lis where lis = ls ++ lis iterate :: (a -> a) -> a -> [a] iterate f e = e : iterate f (f e) -- repeat 5 => [5,5,5,5,...] -- cycle [1,2] => [1,2,1,2,...] -- iterate (+1) 1 => [1,2,3,...]
5 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Манипуляции с бесконечными числовыми списками diff :: (Num a) => [a] -> [a] diff = (y-x) : (diff l) take 25 (diff [x*x | x
6 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Список простых чисел, полученный способом «решета Эратосфена» primes :: [Integer] primes = sieve [2..] where sieve (e:ls) = e : (sieve [x | x