Функциональные языки (на примере Haskell)

Функциональные языки программирования (ФЯП) представляют собой в первую очередь новый (для многих) способ думать о программах и программировании. Часто хорошо написанный функциональный код оказывается гораздо более выразительным и аккуратным, чем эквивалентный императивный или ООП-код.

Большинство современных функциональных языков так же предоставляют некоторые гарантии касательно программ. В частности, Haskell в большинстве случаев гарантирует, что программа не завершится с ошибкой доступа к памяти, как, скажем C++, или с ошибкой преобразования типов, как, скажем, Python или Ruby. Большинство подобных ошибок будут обнаружены на этапе компиляции программы.

В основе функционального программирования лежит простое представление о том, что функции в языке ничем не отличаются от переменных. Обычно к этому добавляют, что функции в целом должны быть функциями в математическом смысле, то есть не должны иметь некого внутреннего состояния и не должны неявно изменять внешнего состояния (окружения). Прямым следствием отсутствия состояния является тот факт, что функция, вызванная с одними и теми же аргументами возвращает одно и то же значение. Следствием неизменности внешнего состояния является отсутствие побочных эффектов. Например, printf в C/C++ принимает некие аргументы, и возвращает число. Но кроме этого, printf выводит символы в терминал. Последнее является побочным эффектом. В общем случае, неявные изменения внешнего (по отношнению к программе) состояния считаются побочными эффектами.

Но если внешнее состояние неизменно, программа неизбежно превращается в некую Кантовскую “вещь в себе” – она не может читать/записывать файлы, терминал, и т.д. Это не выглядит очень полезным. На самом деле, ФЯП выходят из положения, вводя некую псевдопеременную “мир”, которая может явно быть передана главной функции программы (main), и ее измененное состояние явно возвращается главной функцией программы. Таким образом, функциональную программу можно алгебраически представить как некую функцию:

\[ W_{n+1} = P(W_{n}), \]

где $W$ – состояние окружения (“мир”), а $P$ – это программа.

Другая особенность ФЯП, прямо следующая из того, что функции не имеют и не изменяют состояния заключается в том, что в ФЯП очень часто нет “переменных”. Любые выражения являются константами, если смотреть с точки зрения императивных языков. Это свойство называется “ссылочной прозрачностью”: если вы видите, что функция принимает переменную, вы всегда точно знаете, какое значение имеет эта переменная.

Подобный подход значительно упрощает “думание” о программах: больше не нужно держать в голове состояние – код работает ровно так, как читается – никаких скрытых параметров.

Использование чистых функций, помимо прочего, позволяет значительно упростить реализацию функций высших порядков, т.е. функций, оперирующих с функциями (которые тоже могут оперировать с функциями, и так далее). Поэтому, большинство ФЯП имеют поддержку функций высшего порядка “встроенными” в язык интуитивным образом. В качестве небольшого примера, приведу сравнение реализаций функции for_each, работающей со списком на C++ и Haskell.

Функции высшего порядка

#include <list>
#include <iostream>

template<class T, class F>
std::list<T> for_each(F f, const std::list<T> &list) {
    std::list<T> result;
    for(typename std::list<T>::const_iterator i=list.begin(); i!=list.end(); ++i) {
        result.push_back(f(* i));
    }
    return result;
}

// для использования этой функции нам придется объявить функтор

struct UnaryFunction {
    template<class T>
    T operator()(const T &arg) {
        //здесь может быть в общем-то любое действие
        return arg+1;
    }
};

// и использовать его как-то так

int main() {
    std::list<int> x;
    x.push_back(1); x.push_back(2);

    std::list<int> y = for_each<int, UnaryFunction>
                            (UnaryFunction(), x);

    for(std::list<int>::iterator i=y.begin(); i!=y.end(); ++i) {
        std::cout<<* i<<",";
    }
    std::cout<<std::endl;
}

На Haskell аналогичный код будет выглядеть так:

for_each(f,list) = if (null(list))
                   then []
                   else f(head(list)) : for_each(f,tail(list))

-- Мы можем использовать эту функцию, например, так:

main = print (for_each((1+),[1,2]))

На самом деле, вызов функции с аргументами в Haskell является настолько фундаментальным, что не имеет специального синтаксиса, поэтому аналогичный код можно записать так:

for_each f list = if null list
                   then []
                   else f (head list) : for_each f (tail list)

main = print (for_each (1+) [1,2])

На самом деле в языке уже есть такая функция, и она называется map. Вернемся к ней чуть позже.

Каррирование

Очень интересным мометном здесь является использование (1+) для добавления 1. Для этого придется рассказать про нотацию Хаскеля Брукса Карри (американского математика, 1900-1982), в честь которого назван язык. Эта нотация называется частичной аппликацией функций или каррирование.

Вкратце, любая функция нескольких аргументов $f(x,y)$ может быть разложена на последовательное применение нескольких функций одного аргумента. Например, $f(2,3)$ может быть разложена как:

\[ g(y) = f(2,y) \] \[ f(2,3) = h(g(3)) \]

Можно заметить, что функция двух аргументов $f(x,y)$ превращается в функцию одного аргумента $g(y)=f(x,y)$. Это и есть каррирование. Если записать то же самое в нотации Haskell:

g y = f x y

Здесь применима операция, называемая алгебраической эта-редукцией. Повторяющиеся аргументы можно опустить. В результате получаем

g = f x

Какое отношение это имеет к (1+)? Самое прямое. (1+). Сложение является функцией двух аргументов и может быть записано как x+y = (+) x y. Тогда применение к одному аргументу (+) 1 даст нам функцию одного аргумента, которая прибавляет к аргументу 1. (1+) – это просто синтаксическое соглашение (“сахар”), которое сводится к (+) 1.

Порядок применения функции

Чтобы каррирование работало, аргументы функции применяются слева направо (или лево-ассоциативно). Таким образом, выражение вида

f a b c d

Означает то же самое, что

(((f a) b) c) d

Это отвечает на вопрос, почему нельзя записать print for_each (1+) [1,2] и ожидать адекватных результатов (на самом деле такой код просто не скомпилируется, поскольку print for_each не может принимать аргументы)

Существует оператор $, который является право-ассоциативным применением функции. Поэтому код можно записать так:

print $ for_each (1+) [1,2]

Это позволяет слегка экономить на скобках, однако применимость зависит от конкретного случая.

Эта-редукция, композиция функций и pointfree-нотация

Другой способ экономии – это эта-редкукция.

Эта-редукция позволяет писать достаточно компактный и при этом вполне понятный код, опуская “лишние” переменные. Такая нотация называется “pointfree” (аргументы иногда называют “точками”, отсюда такое название). Напишем программу, которая читает строки и выводит их в обратном порядке.

revlines x = unlines (reverse (lines x))

main = getContents >>= return . revlines >>= putStrLn

Пока не обращая внимания на последнюю строчку (считаем что там магия), рассмотрим функцию revlines. Очевидно, что x здесь вполне избыточен. В математике есть нотация композиции функций, обозначаемая точкой:

\[ f(g(x)) = (f\cdot g)(x) \]

Haskell имеет аналогичную нотацию: f (g x) = (f . g) x. Тогда мы можем переписать revlines в виде

revlines x = (unlines . reverse . lines) x

Или, применяя эта-редукцию:

revlines = unlines . reverse . lines

Использование функций высшего порядка возможно и в этом контексте. Скажем, мы можем хотеть не только вывести строки в обратном порядке, но и произвести каую-то другую операцию над массивом строк. Тогда мы можем написать:


withLines f = unlines . f . lines

revlines = withLines reverse

sortlines = withLines sort

takelines = withlines . take

Аннотации типов

Можно заметить, что во всем до сих пор написанном коде нигде не указаны типы. Haskell является строго типизированным языком, но типы указывать не обязательно . Это потому, что Haskell выводит типы автоматически. Тем не менее, для повышения читаемости кода (и для уменьшения вероятности ошибки), типы можно указывать¹. Запишем типы некоторых функций, и обсудим что это значит:

for_each :: (a->b) -> [a] -> [b]

revlines :: String -> String

withLines :: ([String]->[String]) -> String -> String

По соглашению, типы начинаются с заглавной буквы. Если тип обозначен маленькой буквой, то Haskell автоматически выводит его исходя из контекста. Так, например, мы использовали for_each с целыми. Тогда a=Int, b=Int. С тем же успехом, мы могли бы использовать ее со строками и т.д.

Оператор -> – право-ассоциативен (ввиду каррирования), поэтому

a -> b -> c

т.е. “функция принимает два аргумента”, эквивалентно

a -> (b -> c)

т.е. “функция принимает один аргумент и возвращает функцию одного аргумента”

`map` как функция высшего порядка

Попробуем написать свою функцию для работы со строками. Допустим, мы пишем программу, автоматически форматирующую код.

withLines f = unlines . f . lines

indent = (++) "    "

indentLines = withLines indent

main = getContents >>= return . indentLines >>= putStrLn

Получаем чудовищное, по виду, сообщение об ошибке

Couldn't match type ‘Char’ with ‘[Char]’
Expected type: [String] -> [String]
  Actual type: [Char] -> [Char]
In the first argument of ‘withLines’, namely ‘indent’
In the expression: withLines indent

Почему это происходит? Давайте запишем типы всех функций.

withLines :: ([String]->[String]) -> String -> String
withLines f = unlines . f . lines

indent :: String -> String
indent = (++) "    "

indentLines :: ???
indentLines = withLines indent

main = getContents >>= return . indentLines >>= putStrLn

Ошибка становится вполне очевидна: withLines ожидает функцию типа [String]->[String], а мы ему даем String->String. Вообще, String определен как [Char], т.е. список символов. Это объясняет сообщение компилятора.

Вспомним про функцию map, которая производит операцию над каждым элементом массива. Ее тип

map :: (a -> b) -> [a] -> [b]

Подставляя a,b=String, обнаруживаем то, что ищем:

map :: (String -> String) -> ([String] -> [String])

withLines :: ([String]->[String]) -> String -> String
withLines f = unlines . f . lines

indent :: [String] -> [String]
indent = map $ (++) "    "

indentLines :: String -> String
indentLines = withLines indent

main = getContents >>= return . indentLines >>= putStrLn

Оказывается, map – это функция высшего порядка, которая преобразует функцию над элементами в функцию над массивами (списками). Подобные операции называются “поднятием” (lift), поскольку “поднимают” функцию из более простой категории типов в более сложную. Вообще, система типов Haskell сильно основана на теории категорий. Однако про теорию категорий сейчас не будем.

Секционирование операторов

Еще один пример использования функций высшего порядка

import Data.Char (toUpper)

withLines :: ([String] -> [String]) -> String -> String
withLines = (unlines .) . (. lines)

withWords :: ([String] -> [String]) -> String -> String
withWords = (unwords .) . (. words)

yell :: String -> String
yell = (++"!!!") . map toUpper

yellEachWord = withLines $ map $ withWords $ map yell

main = getContents >>= return . yellEachWord >>= putStrLn

Здесь есть достаточно странный синтаксис. Для начала будем иметь ввиду, что любой бинарный оператор (а вообще говоря любая бинарная функция) может быть частично применен как

op a b = ...

op a == (a `op`)

Вообще, `op` – это использование бинарной функции op как бинарного оператора

a `op` b = op a b

C тем же успехом можно частично применить второй аргумент:

op x b == (`op` b) x

Этот синтаксический сахар называется “секционирование операторов”

. – это бинарная функция высшего порядка:

(.) :: (b -> c) -> (a -> b) -> (a -> c)

Соответственно, если мы перепишем, скажем, withLines с аргументом, то получим:

withLines f = ((unlines .) . (. lines)) f
            = (unlines .) (f . lines)
            = (unlines . (f . lines))
            = unlines . f . lines

Типы данных

В примерах раннее мы использовали тип данных списка (массива). Как этот тип устроен? Давайте попробуем сделать пользовательский тип списка.

data Список a = Пусто | Добавить a (Список a)

Это можно прочитать как “список типа a это либо пустой список, либо значение типа a и остальной список типа a (который может быть пустым)”. Haskell кстати понимает UTF-8, поэтому приведенный код абсолютно корректен.

Теперь мы можем записать что-то такое, например:

список = 1 `Добавить` 2 `Добавить` 3 `Добавить` Пусто

В Haskell, естественно, есть встроенный тип списка. Он определен следующим образом:

data [] a = [] | a:[a]

Можно просмотреть параллели. : – это Добавить, или cons, [] – это Пусто, или nil, а Список а – это [a]. Мы можем легко определить собственные операторы:

infixr 5 :-: -- право-ассоциативный с приоритетом 5
(:-:) = Добавить

Или использовать их сразу в определении типа.

Единственное, что встроено в язык – это синтаксис вида [x,y,...], который автоматически преобразуется в x:y:...:[].

Здесь Добавить и Пусто называются конструкторами типа Список. Это функции, которые “конструируют” значение типа Список. Не имеют практически ничего общего с конструкторами объектов в C++/Java.

Несколько примеров с нашим пользовательским типом:

mystery1 = "один" :-: Пусто
mystery2 = "два" :-: mystery1
mystery3 = "три" :-: mystery3
mystery4 = 4 :-: mystery1

С mystery1, mystery2 все должно быть понятно. mystery3 – это бесконечный список, и Haskell все устраивает (поскольку это ленивый язык – значения вычисляются только при использовании), mystery4 – это ошибка типа. Int и String не могут находиться в одном списке.

Аналогично пишутся прочие типы данных.

Шаблоны аргументов

Для простоты, переопределим наш тип списка в латинице и сразу используем оператор:

infixr 5 :-:
data List a = Nil | a :-: List a

Напишем несколько функций для нашего пользовательского списка:

takeOne (x :-: _) = x :-: Nil
takeOne Nil = Nil
dropOne (_ :-: xs) = xs
dropOne Nil = Nil

Выглядит как какая-то черная магия. На самом деле все просто, мы определяем функцию, которая работает только для конкретного конструктора. _ означает только что мы игнорируем это поле. Мы так же могли бы конкретизировать аргументы, например:

isOne (x :-: Nil) = True
isOne _ = False

Шаблоны проверяются в порядке объявления, поэтому во втором случае мы можем просто игнорировать значение.

Если мы не указываем все возможные варианты, то компилятор сообщает об этом, например:

isOne (x :-: Nil) = True

Приводит к сообщению

Pattern match(es) are non-exhaustive
In an equation for ‘isOne’: Patterns not matched: Nil

Нужно иметь ввиду, что программа аварийно завершится, если такой частично определенной функции передать значение, которое она не может обработать.

Тип Maybe

Немного странно кажется, что наша функция takeOne возвращает список, а не значение. Аналогичная библиотечная функция head возвращает значение, однако на пустом списке кидает исключение (да, в Haskell есть исключения, но их стараются избегать по очевидным причинам). Ее можно было бы записать в виде

head (x:_) = x
head [] = undefined

undefined – ключевое слово, которое подходит под любой тип и аварийно завершает программу при попытке вычисления. Другой вариант undefined – это error x, где x имеет вид String. error выведет строку x перед завершением.

На помощь приходит тип Maybe. Он определен так:

data Maybe a = Nothing | Just a

В целом похоже на список, только без списка. takeOne можно переписать в виде:

takeOne (x :-: _) = Just x
takeOne Nil = Nothing

Выглядит несколько более осмыслено, чем вариант со списком и гораздо более безопасно, чем undefined.

Попробуем написать поиск символа в строке с использованием типа Maybe:

findChar :: Char -> String -> Int -> Maybe Int
findChar c (x:xs) pos = if x==c
                        then Just pos
                        else findChar c xs (pos+1)
findChar _ [] _ = Nothing

Pattern guards

Предыдущий код можно переписать несколько короче:

findChar c (x:xs) pos | x==c = Just pos
                      | otherwise = findChar c xs (pos+1)
findChar _ [] _ = Nothing

Этот синтаксис называется “pattern guards”, или ограничители шаблонов в вольном переводе на русский. По сути, если выражение после | вычисляется как True, то шаблон срабатывает. Если нет – то проверяется следующий ограничитель, или следующий шаблон, если это был последний. otherwise – это просто более читаемый синоним для True.

В ограничителях так же возможно производить сравнения шаблонов. Синтаксис для этого:

f ... | pattern <- expression = ...

Тогда код выше можно переписать в виде:

findChar c list pos | (x:_) <- list, x==c = Just pos
                    | (_:xs) <- list = findChar c xs pos
                    | otherwise = Nothing

Классы типов

На самом деле мы можем записать более общий вариант поиска элемента в списке, практически ничего не делая:

findChar :: Eq a => a -> [a] -> Int -> Maybe Int
findChar c (x:xs) pos | x==c = Just pos
                      | otherwise = findChar c xs (pos+1)
findChar _ [] _ = Nothing

Мы изменили только сигнатуру типа, остальное осталось прежним. Сигнатура выглядит странновато: в ней появилось выражение Eq a =>. Оно означает, что тип a принадлежит классу Eq – классу типов, для которых определена эквивалентность, т.е. опреатор (==).

Eq определен следующим образом:

class Eq a where
  (==) :: a -> a -> Bool

Видно, что это просто сигнатура типа. Чтобы определить реализацию для конкретного типа, определяется экземпляр класса:

instance Eq Char where
  a == b = ...

Каким конкретно образом реализовано сравнение символов – довольно долгая история. Примитивные типы типа Int, Char или скажем Double достаточно глубоко встроены в язык. Мы, однако, можем определить экземпляры для более сложных типов:

instance Eq a => Eq (Maybe a) where
  (Just a) == (Just b) = a == b
  Nothing == Nothing = True
  _ == _ = False

Здесь мы опять вводим ограничение на класс. По сути мы утверждаем, что для всех типов a в классе Eq существует тип Maybe a, так же в классе Eq. Ничто не мешает добавлять собственные типы.

Классы типов позволяют писать обобщенные, и при этом типобезопасные функции.

Опять про `Maybe`

Тип Maybe достаточно простой и при этом удивительно полезный. Очень многие функции, которые возможно определены могут использовать этот тип в качестве возвращаемого значения. Например:

elemIndex :: a -> [a] -> Maybe Int
lookup :: k -> Map k v -> Maybe v
stripPrefix :: [a] -> [a] -> Maybe [a]

Это гораздо лучше, чем возвращать NULL, как в C/C++. Во-первых, глядя на сигнатуру типа, сразу становится ясно, чего можно ожидать от функции. Во-вторых, компилятор не позволит производить вычисления с несуществующим значением. Если в “классических” языках типы в основном служат компилятору, то в функциональных типы служат в первую очередь программисту.

Очевидный вопрос с Maybe заключается в следующем: допустим у нас есть функция

takeOne (x:_) = Just x
takeOne [] = Nothing

Рассмотрим такой код:

takeOne [1,2,3] + 1

Каков результат такого кода? Правильный ответ – ошибка типа. 1 имеет тип Int, в то время как takeOne возвращает тип Maybe Int. Проблема очевидна. Наивное решение этой проблемы в том, чтобы написать условие:

case takeOne [1,2,3] of
  Nothing -> undefined
  Just x -> x+1

Однако ясно, что для сколько-нибудь сложных выражений это становится весьма трудоемкой задачей.

Теперь давайте вспомним, что, когда я говорил про map, я сказал, что эта функция “поднимает” свой первый аргумент в категорию списков. Эта же концепция применима ко всем производным типам. В языке сущесвтует обобщенная функция fmap. Посмотрим, как она работает:

fmap (+1) (takeOne [1,2,3])

Это выражение возвращает Just 2. fmap “поднимает” свой аргумент в категорию производных типов. Каких именно – компилятор выводит автоматически из контекста.

Тип fmap определен как

fmap :: Functor f => (a -> b) -> f a -> f b

Здесь используется класс Functor, единственное требование которого – чтобы был определен fmap. Для Maybe экземпляр определяется тривиально:

instance Functor Maybe where
  fmap f (Just x) = Just $ f x
  fmap _ Nothing = Nothing

В общем случае класс Functor – это класс типов, принимающих один аргумент типа. Другой пример функтора – список. Таким образом, map является всего лишь частным случаем fmap.

Монады

Пока скажу только, что Maybe, и список являются монадами. Понятие монады происходит из теории категорий. Это понятие в большинстве функциональных языков является ключевым, поскольку, например, Haskell, инкапсулирует состояние окружения (то, которое функции не изменяют) в монаде IO (ввод-вывод). Наконец мы можем записать сигнатуру для main:

main :: IO ()

Функция main возвращает “пустоту” (на самом деле читается как unit, и аналогично по смыслу void в С) в монаде IO. IO, в свою очередь, где-то “внутри” содержит информацию о состоянии окружения.

Сточка, которая часто нам встречалась

main = getContents >>= return . f >>= putStrLn

использует следующие функции:

getContents :: IO String
return :: Monad m => a -> m a
putStrLn :: String -> IO ()
(>>=) :: Monad m => m a -> (a -> m b) -> m b

return и (>>=) (читается как bind) определены в классе Monad. return просто “поднимает” значение в монаду, а bind берет значение в монаде и передает его в функцию, возвращающую монаду. При этом некое “состояние”, инкапсулированное монадой (если оно есть), может неявно передаваться из функции в функцию через оператор bind.

Для интересующихся, хорошее объяснение:

https://www.youtube.com/watch?v=ZhuHCtR3xq8

Если есть интерес, выделим лекцию на продолжение.

На самом деле иногда однозначно определить типы невозможно, и тогда аннотации все-таки необходимы. Так же необходимо использовать аннотации при написании обобщенных функций↩︎

23. Функциональные языки на примере Haskell