Алгебраический тип данных – два подхода. Карринг. Сортировка, быстрая сортировка Хоара, лямбда-функции.
Алгебраический тип данных неформально можно определить как множество значений, представляющих собой некоторые контейнеры, внутри которых могут находиться значения каких-либо иных типов.
Множество таких контейнеров и составляет сам тип данных, множество его значений.
Алгебраический тип данных — размеченное объединение декартовых произведений множеств или, другими словами, размеченная сумма прямых произведений множеств.
Здесь (x, i) — упорядоченная пара, в которой элементу x приписан индекс множества, из которого элемент попал в размеченное объединение.
Теоретико-множественное описание АДТ
Древовидное представление (нотация Ч. Э. Хоара)
синтаксически-ориентированное конструирование АТД
Каррирование (карринг)
Функция f (x, y) = x + y двух переменных x и y может быть рассмотрена как функция одной переменной x, возвращающая функцию одной переменной y.
Такой приём работает точно так же для функций любой арности.
Это показывает, что функции многих переменных могут быть без проблем выражены в λ-исчислении и являются «синтаксическим сахаром».
Описанный процесс превращения функций многих переменных в функцию одной переменной называется карринг (также: каррирование), в честь американского математика Хаскелла Карри, хотя первым его предложил М. И. Шейнфинкель – российский математик.
Функциональный подход сосредоточен на вычислении выражений, а не на выполнении команд.
Фактически, функциональная программа – это выражение, и ее выполнение соответствует вычислению выражения.
Лямбда-функции
В основу λ-исчисления положены две фундаментальные операции: аппликация и абстракция. Аппликация означает применение или вызов функции по отношению к заданному значению. Её обычно обозначают f\ a, где f — функция, а a — значение. Это соответствует общепринятой в математике записи f(a), которая тоже иногда используется, однако для λ-исчисления важно то, что f трактуется как алгоритм, вычисляющий результат по заданному входному значению. В этом смысле аппликация f к a может рассматриваться двояко: как результат применения f к a, или же как процесс вычисления f\ a Абстракция или λ-абстракция в свою очередь строит функции по заданным выражениям. λ функция от аргумента x, которая имеет вид t[x] обозначает функцию x t[x]. Таким образом, с помощью абстракции можно конструировать новые функции.
Использование λ -исчисления
Т.к. функциональная парадигма программирования основана на λ-исчислении, то вполне закономерно, что все функциональные языки поддерживают нотацию для описания λ-абстракций – т.е. объектов “не имеющих” фиксированного типа.
Haskell не обошел стороной и этот аспект, если есть необходимость в определении какой-либо функции через λ-абстракцию.
Кроме того, через λ-абстракции можно определять анонимные функции (например, для единичного вызова).
Быстрая сортировка Хоара на языке Haskell.
quickSort [] = []
quickSort (h: t) = quickSort [y | y <- t, y < h] ++ [h] ++ quickSort [y | y <- t, y >= h]
1.Если список пуст, то результатом также будет пустой список.
2.Иначе (если список не пуст) выделяется голова (первый элемент) и хвост (список из оставшихся элементов, который может быть пустым). В этом случае результатом будет являться конкатенация (сращивание) отсортированного списка из всех элементов хвоста, которые меньше либо равны голове, списка из самой головы и списка из всех элементов хвоста, которые больше головы.
Все операции с памятью выполняются автоматически. При создании какого-либо объекта под него автоматически выделяется память.
После того как объект выполнит своё предназначение, он вскоре будет также автоматически уничтожен сборщиком мусора, который является частью любого функционального языка.