|
|
|
|
| aexp
| ->
| [ exp | qual1,..., qualn ]
| (описание списка, n>=1)
|
| qual
| ->
| pat <- exp
| (генератор)
|
|
| |
| let decls
| (локальное объявление)
|
|
| |
| exp
| (страж)
|
|
|
|
|
| Перевод:
|
|
|
| выражение-аргумента
| ->
| [ выражение | квалификатор1,..., квалификаторn ]
| (описание списка, n>=1)
|
| квалификатор
| ->
| образец <- выражение
| (генератор)
|
|
| |
| let списки-объявлений
| (локальное объявление)
|
|
| |
| выражение
| (страж)
|
Описание списка имеет вид [ e | q1,..., qn ], n>=1, где квалификаторы qi являются
- или генераторами вида p <- e, где p --- образец типа t, а e --- выражение типа [t],
- или стражами, которые являются произвольными выражениями типа Bool,
· или локальными связываниями имен, которые обеспечивают новые определения, используемые в генерируемом выражении e или последующих стражах и генераторах.
Такое описание списка возвращает список элементов, порожденный путем вычисления e в последовательных окружениях, созданных вложенным вычислением вглубину генераторов в списке квалификаторов. Связывание имен переменных происходит согласно правилам обычного сопоставления с образцом, и если сопоставление завершится неудачей, то соответствующий элемент списка будет просто пропущен. Таким образом,
[ x | xs <- [ [(1,2),(3,4)], [(5,4),(3,2)] ],
(3,x) <- xs ]
порождает список [4,2]. Если квалификатор является стражем, то, для того чтобы предшествующее сопоставление с образцом завершилось успешно, необходимо, чтобы значение квалификатора равнялось True. Как обычно, связывания имен в описаниях списков могут скрыть связывания имен во внешних областях видимости, например,
| [ x | x <- x, x <- x ]
| =
| [ z | y <- x, z <- y]
|
| [ e | True ]
| =
| [e]
|
| [ e | q ]
| =
| [ e | q, True ]
|
| [ e | b, Q ]
| =
| if b then [ e | Q ] else []
|
| [ e | p <- l, Q ]
| =
| let ok p = [ e | Q ]
|
|
|
| ok _ = []
|
|
|
| in concatMap ok l
|
| [ e | let decls, Q ]
| =
| let decls in [ e | Q ]
|
Трансляция:
Для описаний списков выполняются следующие тождества, которые могут быть использованы в качестве трансляции в ядро:
где e --- выражения, p --- образцы, l --- выражения, значениями которых являются списки, b --- булевы выражения, decls --- списки объявлений, q --- квалификаторы, а Q --- последовательности квалификаторов. ok --- новая переменная. Функция concatMap и булево значение True определены в Prelude.
10) Локальные определения. Лямбда – выражения (Haskell).
Вместо использования уравнений для определения функции мы также можем определять их «анонимно», через лямбда-абстракцию. Например, функция, эквивалентная inc, может быть записана как \x -> x+1. Аналогично, функция add эквивалентна \x -> \y -> x+y. Вложенная лямбда-абстракция, подобная этой, может быть записана с использованием эквивалентной сокращённой формы: \x y -> x+y. Фактически уравнения:
inc x = x+1
add x y = x+y
на самом деле являются сокращениями для:
inc = \x -> x+1
add = \x y -> x+y
Позже мы подробнее обсудим эту эквивалентность.
В общем случае, если x имеет тип t 1, а exp имеет тип t 2, то \x->exp имеет тип t 1 ->; t 2.
11) Функционалы и другие функции высших порядков (Haskell).
В функциональных языках функции могут быть переданы другим функциям в качестве аргумента или возвращены в качестве результата. Функции, принимающие функциональные аргументы, называются функциями высших порядков или функционалами. Самый, пожалуй, известный функционал, это map. map применяет некоторую функцию ко всем элементам списка, формируя из результатов другой список. Например определив функцию возведения целого числа в квадрат как:
square:: Int -> Int
square n = n * n
мы можем воспользоваться этой функцией для возведения в квадрат всех элементов списка
l2 = map square [1, 2, 3, 4] -- результат - список [1, 4, 9, 16]
Каждый тип имеет литералы, например тип Boolean имеет литералы True и False, а тип Char имеет 256 литералов представляющих ASCII символы. Функциональный тип также имеет свои литералы, которые являются ничем иным, как безымянными функциями. Функциональные литералы называются лямбда-абстракциями (это название появилось из лямбда-исчисления Чёрча) или просто лямбдами. Например для получения списка кубов можно воспользоваться записью
l3 = map (\x -> x * x * x) [1, 2, 3, 4] -- результат - список [1, 8, 27, 64]
Функции, возвращающие другие функции, кажутся на первый взгляд несколько более специфичными. В самом деле, куда это можно применять? В функциональных языках они применяются повсеместно. Для примера определим два варианта функции сложения:
sum1:: (Int, Int) -> Int
sum1 (n, m) = n + m
sum2:: Int -> Int -> Int
sum2 n m = n + m
Вопреки первому впечатлению функция sum1 принимает всего один аргумент - пару чисел, и возвращает результат - их сумму. Функция sum2 (эквивалентная стандартному оператору (+)) - пример частично вычисляемой функции. Эта функция принимает в качестве аргумента число (типа Int) и возвращает функцию прибавляющую это число к своему аргументу. Зачем это нужно? Функция sum2 позволяет легко определять свои частные случаи. Например - функция инкремент, увеличивающая свой аргумент на 1 определяется как частный случай sum2 следующим образом:
inc:: Int -> Int
inc = sum2 1
Функция map - тоже пример частично-вычисляемой функции. Эта функция принимает в качестве аргумента функцию и возвращает функцию принимающую список и возвращающую другой список. Это легко понять если взглянуть на пример:
-- sins принимает список действительных чисел (типа Double)
-- и возвращает список их синусов
sins:: [Double] -> [Double]
sins = map sin
