Математическое введение в декларативное программирование. Зюзысов В.М. - 78 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

10.3 Ленивые вычисления
Строгая семантика обычных языков программирования требует, чтобы перед вы-
числением значения функции, значения аргументов функции были вычислены. Нестрогая
семантика подразумевает, что аргументы функции будут вычисляться только тогда, когда
возникнет абсолютная необходимость в их значениях. Такие функциональные языки на-
зываются «ленивыми». Реализация ленивых функциональных языков – это достижение
последнего времени. Язык Haskell является ленивым языком. Рассмотрение следующего
примера пояснит нам суть ленивых вычислений. Пусть вызов функции
g 55
есть незавершаемое (бесконечное) или ошибочное вычисление (скажем содержащее деле-
ние на ноль), но вычисление
f 7 (g 55) 0
может быть, тем не менее, успешным в ленивом языке, если функция f
такова, что игно-
рирует свой второй аргумент (если первый, скажем, равен 7). Это свойство гибкости языка
может быть очень полезно также в оперировании с бесконечными структурами данных.
Важным следствием ленивых вычислений появляется принципиальная возмож-
ность создавать бесконечные структуры данных.
ones :: [Int]
ones = 1 : ones
numsFrom :: Int -> [Int]
numsFrom n = n : numsFrom (n+1)
Таким образом, numsFrom n
– бесконечный список последовательных целых, начинаемый
с
n
. Используя этот список, мы можем создать бесконечный список квадратов:
squares :: [Integer]
squares = map (^2) (numsfrom 0)
Когда мы собираемся напечатать что-нибудь, нам необходима функция, которая отрезает
от бесконечных списков конечную часть подходящего размера. Функция take возвращает
первые k элементов списка:
take :: Int -> [a] -> [a]
take 0 x = [] -- два базовых случая: k = 0
take k [] = [] -- или список пустой
take k (x:xs) = x : take (k-1) xs
Сейчас можно напечатать часть списка:
> take 5 ones
[1,1,1,1,1]
> take 5 (numsFrom 10)
[10,11,12,13,14]
> take 5 squares
[0,1,4,9,16]
Функция
zip превращает два списка в список упорядоченных пар. Если списки
имеют различную длину, то длина результата совпадает с длиной более короткого списка.
zip (x:xs) (y:ys) = (x,y) : zip xs ys
78

Страницы