Функции в Haskell

Синтаксис применения функции

Синтаксис двух последовательных идентификаторов означает применение функции foo к своему аргументу bar:

foo bar

На Haskell вызов функции не требует заключения аргумента в скобки. 

Скобки используются для группировки аргументов:

acos (cos pi)

Функция нескольких аргументов:

max 5 42

Операция применения функции ассоциативна влево:

(max 5) 42

Функция max последовательно применяется к двум аргументам.
Компилятор понимает конструкцию f x y как (f x) y, а не наоборот f (x y).

Выражение (max 5) это так называемое частичное применение функции. В общем виде его можно сформулировать следующим образом: если у нас имеется функция N переменных и мы смотрим на неё как на функцию N переменных, то мы можем взглянуть на неё с другой стороны и сказать, что это функция одной переменной возвращающая нам функцию N - 1 переменной.

3 + sin 42

3 + (max 5) 42

Синтаксис объявления пользовательской функции

Функция, которая осуществляет суммирование квадратов двух переданных в неё аргументов:

sumSquares x y = x ^ 2 + y ^ 2

rock'n'roll = 42

Имя функции и имена формальных параметров должны начинаться с символа в нижнем регистре. А символы в верхнем регистре служат для определения типов данных.

Функция трех аргументов, которая вычисляет длину трехмерного вектора:

lenVec3 x y z =  sqrt (x ^ 2 + y ^ 2 + z ^ 2)

Для определения функции в интерпретаторе GHCi нам нужно использовать ключевое слово let.

let sumSquares x y = x ^ 2 + y ^ 2

Свойство чистоты функции

Важной характеристикой отличающей функциональные языки от императивных служит свойство чистоты функции. Все функции в Haskell являются чистыми. Это означает, что значение функции полностью определяется значениями переданных в неё аргументов. Никакие другие источники данных не могут влиять на результат возвращаемый функцией. Если нужно чтобы функция откуда-то брала данные, то нужно передать ей этот источник данных в качестве аргумента.

Функция, которая не принимает ни одного аргумента это константа. Такая функция всё время возвращает одно и то же значение независимо ни от каких обстоятельств.

Prelude> let fortyTwo = 39 + 3
Prelude> fortyTwo
42

На Haskell нельзя определить функцию не принимающую никаких аргументов, которая бы возвращала разные значения при разных вызовах.

Механизм определения функций с помощью частичного применения

На любую функцию мы можем смотреть как на функцию одного аргумента возвращающую некоторую функцию.

Prelude> let max5 x = max 5 x
Prelude> max5 4
5
Prelude> max5 42
42

Альтернативный синтаксис определения функции:

Prelude> let max5' = max 5
Prelude> max5' 4
5
Prelude> max5' 42
42

Мы сократили слева и справа дополнительный аргумент x. И написали, что функция max5' это просто частично примененная функция max. Таким образом можно определять функцию не указывая всех аргументов. Соответствующий стиль программирования называется бесточечным.


Часто дизайн функций в Haskell настраивается таким образом чтобы частичное применение было удобным;

Prelude> let discount limit proc sum = if sum >= limit then sum * (100 - proc) / 100 else sum
Prelude> let standardDiscount = discount 1000 5
Prelude> standardDiscount 2000
1900.0
Prelude> standardDiscount 900
900.0

Параметры limit и proc меняются редко. А вот параметр sum меняется часто. Фактически при каждом вызове этой функции.


Предположим, мы разрабатываем на Haskell интерфейс системы перевода для естественных языков. Он должен содержать функцию translate с параметрами text, languageFrom и languageTo. Для того чтобы было удобно реализовывать следующие функции:

• translateFromSpanishToRussian, 
• translateFromEnglishToRussian 
• и translateToRussian 

надо расположить параметры в таком порядке: translate languageTo languageFrom text.

Оператор над типами ->

Для того чтобы написать тип функции нужно написать тип её аргумента и тип результата этой функции. В Haskell для описания типа функции служит оператор -> это бинарный оператор у которого левый операнд это тип аргумента, а правый операнд это тип результата. Стрелочка находится между левым и правым операндом т,к, это инфиксный оператор.

Prelude> :t not
not :: Bool -> Bool
Prelude> (&&) False True
False
Prelude> ((&&) False) True
False

Тип последнего выражения может быть записан следующим образом:
Bool -> (Bool -> Bool)
Оператор над типами рассматривается как право-ассоциативный. Поэтому Bool -> (Bool -> Bool) можно переписать как Bool -> Bool -> Bool

Prelude> :t (&&)
(&&) :: Bool -> Bool -> Bool

Вспомним функцию discount, которая возвращала итоговую сумму покупки с возможной скидкой. В качестве параметров ей передавались сумма без скидки sum, процент скидки proc, причем скидка начислялась, если переданная сумма превышает порог limit. Все эти параметры, как и возвращаемое значение, можно хранить в типе Double. Тип функции можно задать в файле исходного кода вместе с ее определением:

discount :: Double -> Double -> Double -> Double
discount limit proc sum = if sum >= limit then sum * (100 - proc) / 100 else sum

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

standardDiscount :: Double -> Double
standardDiscount = discount 1000 5

Рассмотрим функцию twoDigits2Int, которая принимает два символа и возвращает число, составленное из этих символов, если оба символа числовые, и 100 в противном случае. (Первый символ рассматривается как количество десятков, второй — единиц.)

import Data.Char
twoDigits2Int :: Char -> Char -> Int
twoDigits2Int x y = if isDigit x && isDigit y then digitToInt x * 10 + digitToInt y else 100

GHCi> twoDigits2Int '4' '2'
42

Рекурсия

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

• вызовы функции в правой части должны осуществляться на значениях параметра отличного от формального параметра функции;
• рекурсивные вызовы должны где-то прерываться (должно быть так называемое терминирующее условие).

Факториал

factorial n = if n == 0 then 1 else n * factorial (n - 1)

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

factorial5 n | n >= 0    = helper 1 n
             | otherwise = error "arg must be >= 0"
helper acc 0 = acc
helper acc n = helper (acc * n) (n - 1)

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

Двойной факториал

Рассмотрим функцию, вычисляющую двойной факториал, то есть произведение натуральных чисел, не превосходящих заданного числа и имеющих ту же четность. Например: 7!!=7⋅5⋅3⋅1, 8!!=8⋅6⋅4⋅2. Предполагается, что аргумент функции может принимать только неотрицательные значения.

doubleFact :: Integer -> Integer
doubleFact n = if n <= 0 then 1 else n * doubleFact (n - 2)

Последовательность чисел Фибоначчи

Последовательность чисел Фибоначчи 0,1,1,2,3,5,8,13,21,… легко определить рекурсивно, задав два первых терминирующих значения и определив любое последующее как сумму двух непосредственно предыдущих:
F₀=0
F₁=1
F_n=F_n−1+F_n−2

На Haskell данное определение задаётся следующей функцией:

fibonacci :: Integer -> Integer
fibonacci n  | n == 0 = 0
             | n == 1 = 1
             | n > 1 = fibonacci (n - 1) + fibonacci (n - 2)
             | n < 0 = fibonacci (n + 2) - fibonacci (n + 1)
             | otherwise = undefined

Реализация функции для вычисления числа Фибоначчи, основанная на прямом рекурсивном определении, крайне неэффективна - количество вызовов функции растет экспоненциально с ростом значения аргумента. GHCi позволяет отслеживать использование памяти и затраты времени на вычисление выражения, для этого следует выполнить команду :set +s:

*Fibonacci> :set +s
*Fibonacci> fibonacci 30
832040
(16.78 secs, 409,318,904 bytes)

С помощью механизма аккумуляторов можно написать более эффективную реализацию, имеющую линейную сложность (по числу рекурсивных вызовов):

fibonacci' :: Integer -> Integer
fibonacci' n = helper n 0 1
helper n a b | n == 0 = a
             | n > 0  = helper (n - 1) b (a + b)
             | n < 0  = helper (n + 1) b (a - b)
             | otherwise = undefined

Функции высших порядков

Функцией высших порядков называется функция, которая принимает в качестве аргумента другую функцию. В императивных языках функции высших порядков встречаются редко. В качестве примера можно привести функцию сортировки из стандартной библиотеки языка Си. В качестве первого аргумента в функцию сортировки передается бинарный предикат сравнения с помощью которого массив, который передается в качестве второго аргумента и сортируется. В функциональных языках и в Haskell функции высших порядков используются очень часто.

Prelude> :t ($)
($) :: (a -> b) -> a -> b

Это полиморфный тип. Оператор доллар представляет собой функцию двух аргументов. Его левый операнд или первый аргумент (a -> b) это функция. Его правый операнд a это значение произвольного типа. Оператор доллар просто применяет свой первый аргумент (a -> b) ко своему второму аргументу a. Поэтому здесь необходимо чтобы типы были согласованы. Тип второго аргумента оператора доллар должен совпадать с типом параметра функции, которая передается в первом аргументе. Более того результатом выполнения оператора доллар служит результат выполнения функции, которая передана в качестве первого аргумента. Поскольку тип результата это b то результатом выполнения оператора доллар служит тип b.


Следующее применение допустимо только когда a и b это одно и то же.

Prelude> let apply2 f x = f (f x)
Prelude> :t apply2
apply2 :: (t -> t) -> t -> t
Prelude> apply2 (+5) 22
32
Prelude> apply2 (++ "AB") "CD"
"CDABAB"

Первым аргументом действительно является функция, но аргумент и возвращаемое значение имеют один и тот же тип. А вторым аргументом является значение этого самого типа и возвращаемым значением тоже служит значение этого типа. Таким образом функцию apply2 можно применять на более ограниченном наборе функций чем доллар. Если доллар полиморфен по аргументу и возвращаемому значению, то apply2 полиморфна только по одному параметру.


Функция flip из стандартной библиотеки определена следующим образом: flip f y x = f x y.

Prelude> flip (/) 4 2
0.5
Prelude> (/) 4 2
2.0
Prelude> flip const 5 True
True
Prelude> :t flip
flip :: (a -> b -> c) -> b -> a -> c
Prelude> :t flip const
flip const :: b -> c -> c

{- В модуле Data.Function определена полезная функция высшего порядка -}
on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
on op f x y = f x `op` f y
{- Она принимает четыре аргумента: 
 1) бинарный оператор с однотипными аргументами (типа b), 
 2) функцию f :: a -> b, возвращающую значение типа b, 
 3,4) и два значения типа a. 
Функция on применяет f дважды к двум значениям типа a и передает результат в бинарный оператор.

Используя on можно, например, записать функцию суммирования квадратов аргументов так: -}
sumSquares = (+) `on` (^2)

{- Функция multSecond, перемножающая вторые элементы пар, реализована следующим образом -}
multSecond = g `on` h
g = (*)
h = snd

Анонимные функции

В Haskell как и в математике функции обычно именованы. Когда нам нужно вызвать какую-нибудь функцию мы обращаемся к ней по имени. Однако есть и альтернативный подход, который называется анонимные функции.

Prelude> (\x -> 2 * x + 7) 10
27
Prelude> let f' = (\x -> 2 * x + 7)
Prelude> f' 10
27

Это анонимная функция или лямбда-функция.

Существует синтаксический сахар упрощения записи.

Prelude> let lenVec x y = sqrt $ x^2 + y^2
Prelude> let lenVec x = \y -> sqrt $ x^2 + y^2
Prelude> let lenVec = \x -> \y -> sqrt $ x^2 + y^2
Prelude> lenVec 3 4
5.0
Prelude> let lenVec = \x y -> sqrt $ x^2 + y^2
Prelude> lenVec 3 4
5.0

Анонимные функции применяются в использовании функций высших порядков.

module Demo where

import Data.Function

sumFstFst = (+) `on` helper where helper pp = fst $ fst pp

sumFstFst' = (+) `on` (\pp -> fst $ fst pp)

p1 = ((1,2),(3,4))
p2 = ((3,4),(5,6))

{- Функция on3, имеет семантику, схожую с on, но принимает в качестве первого аргумента трехместную функцию -}
on3 :: (b -> b -> b -> c) -> (a -> b) -> a -> a -> a -> c
on3 op f x y z = op (f x) (f y) (f z)

{- Сумма квадратов трех чисел может быть записана с использованием on3 так -}
sum3squares = (\x y z -> x+y+z) `on3` (^2)

Каррированные и некаррированные функции

При синтаксисе вызова функций в Haskell можно перечислить не все аргументы, а только их часть. Несколько первых аргументов функции можно указать, а остальные отбросить. Эта идея частичного применения функций была придумана Хаскеллом Карри и в честь него такие функции с аргументами передающимися по одному называют каррированными. В Haskell не все функции являются каррированными. В Haskell можно определять функции над кортежами. В этом случае синтаксис вызова функций будет выглядеть также как в обычных языках:
имя_функции ( первый_аргумент, второй_аргумент )

Prelude> fst (1,2)
1

Каррирование - процедура перехода от некаррированных функций к функциям, которые принимают аргументы по одному. Представьте, что у нас есть функция высшего порядка, например комбинатор on, он ожидает в качестве 2 из своих 4 аргументов функции. Первый аргумент это функция двух аргументов, которая является каррированной. В языке Haskell есть специальный комбинатор curry, который выполняет переход от некаррированной функции к каррированной. В следующем примере curry превращает функцию заданную над парой в стандартную каррированную функцию двух аргументов.

*Demo> :t on
on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
*Demo> :t curry fst `on` (^2)
curry fst `on` (^2) :: Num b => b -> b -> b

Еще пример, некаррированная функция avg:

avg :: (Double,Double) -> Double
avg p = (fst p + snd p) / 2

Функция curry avg `on` (^2) это функция, которая вычисляет среднее значение квадратов  двух переданных в неё значений.

Устройство функции curry:

Prelude> let cur f x y = f (x,y)
Prelude> :t cur
cur :: ((t1, t2) -> t) -> t1 -> t2 -> t
Prelude> :t curry
curry :: ((a, b) -> c) -> a -> b -> c

В качестве первого аргумента она принимает некаррированную функцию, т.е. функцию над парой, а превращает её в качестве возвращаемого значения в каррированную функцию в которую аргумента передаются последовательно.

Есть и обратная функция uncurry:

Prelude> :t uncurry
uncurry :: (a -> b -> c) -> (a, b) -> c

Выражение curry id эквивалентно (,).

Prelude> :t curry id
curry id :: a -> b -> (a, b)
Prelude> :t (,)
(,) :: a -> b -> (a, b)

Выражение uncurry (flip const) эквивалентно snd.

Prelude> :t uncurry (flip const)
uncurry (flip const) :: (b, c) -> c
Prelude> :t snd
snd :: (a, b) -> b

В модуле Data.Tuple стандартной библиотеки определена функция swap :: (a,b) -> (b,a), переставляющая местами элементы пары:

GHCi> swap (1,'A')
('A',1)

Эта функция может быть выражена в виде:

Prelude> let swap = uncurry (flip (,))
Prelude> swap (1,'A')
('A',1)

Строгие и нестрогие функции

Ленивые вычисления приводят к тому что во многих ситуациях можно элиминировать незавершаемость программ.

const42 :: a -> Int
const42 = const 42

Функция const42 игнорирует полностью значение аргумента, поэтому в рамках ленивой модели вычислений, если в нее передать в качестве аргумента какое-нибудь сложное вычисление, то это вычисление никогда не произойдет. А это означает, что в качестве аргумента const42 можно передавать любую в том числе и незавершающуюся программу.

*Demo> const42 True
42
*Demo> const42 123
42
*Demo> const42 (1+3)
42
*Demo> const42 undefined
42

Функции подобные const42 называются нестрогими функциями. Если в функцию передано в качестве аргумента расходящееся вычисление, а результатом является какое-то значение не расходящееся, то такая функция называется нестрогой. Строгой называется функция такая, что если мы передаем в нее расходящийся аргумент, то значение этой функции обязательно является расходящимся. Функция двух аргументов может быть строгой или нестрогой по второму аргументу в зависимости от значения своего первого аргумента. Анализ строгости необходим для того чтобы делать программу на Haskell очень эффективной.