Парадигма функціонального програмування. Знайомство з мовою Haskell

ефектами (червоність).




Функціональне програмування. Вступ (1/2)
Чистота: обчислення з одними

аргументами завжди дає один і той самий результат!

g

f

h

Заміна виразу на результат обчислення виразу.
Спрощене тестування.
Природні підходи до розпаралелювання.
Спрощена інтеграція (інтеграція – один з найбільших ризиків в інженерії ПС).

функціональних програм фактично спряжена з уточненням аплікації (застосуванні функції до

аргументу). Хоч останнє, як виявляється, не таке вже й просте, тим не менше теоретичні засади давно відомі. Це – лямбда-числення.

Лямбда-числення, лише кілька штрихів:
чисте лямбда-числення – це числення анонімних функцій;
бета-редукція як основа трактування аплікації (засади операційної семантики);
можливі різні стратегії використання бета-редукцій, зокрема, є стратегія, спряжена із так званими лінивими обчисленнями, є стратегія, спряжена із так званими енергійними обчисленнями;
застосування теореми про нерухому точку (теореми Чорча-Россера) для функцій із рекурсивними визначеннями.

Функціональне програмування. Вступ (2/2)

їх перелік із статті за адресою
http://www.ibm.com/developerworks/ru/library/ l-haskell/?S_TACT=105AGX99&S_CMP=GR01

Компілятори й

інші засоби розробки.
Розподілена система керування версіями Darcs.
Віконний менеджер xmonad.
Сервер Web-додатків HAppS.
Інтерпретатор/компілятор Pugs для мови Perl 6.
Операційна система House.
Мова опису апаратних засобів Lava.
Система обробки натуральної мови LOLITA.
Системи доведення теорем Equinox / Paradox і Agda.

Haskell де-факто є стандартом мов функціонального програмування.

Haskell

‘H’, ‘a’, …;
Bool - True, False.

Засоби конструювання складених значень-констант і

типів:
списки;
кортежі;
функції.
(Функції також є значеннями так званого першого класу – вони можуть бути як аргументами, так і результатами обчислення інших функцій.)

Haskell. Типи даних

Використовується при каррінгу

Haskell – строго типізована мова.
Типи даних програми можна визначити статично (з тексту програми), не потребуючи обов’язкового виконання програми

(Однозв'язні) списки та (незмінні за розміром) кортежі – є вбудованими складеними типами

Механізм виведення типів

рядків

Pair = (a,b)
type Vector = (Double, Double)
type Name =

String
Синоніми типів задають нові імена для існуючих типів (нові типи не визначаються!).
Вони можуть підвищувати читабельність програми за рахунок більшої мнемонічними.

сімейство будь-яких типів списків з (однотипними!) елементами з a. (Мова

ведеться про сімейство — оскільки тип a не уточнюється, тобто вважається присутнім квантор a. При цьому a природно розглядати як змінну типу.
Загалом, поліморфний тип – це тип, що задається виразом, у якому всі змінні типу розглядаються як зв'язані кванторами узагальнення.

Ще один приклад.

Haskell. Типи даних. Поліморфні типи

Як це розуміти?

?

функцій за допомогою одного рівняння:





Swap є прикладом, відповідно, поліморфної функції.

Вона може бути застосована до будь яких пар (двоелементних кортежів).

swap (x, y) = (y, x)

:set prompt >

Функціональний тип!

Зміна підказки

Параметричний поліморфізм (чистий)

Маємо єдину реалізацію для різних типів параметрів

типізації з програміста.
Основний тип виразу чи функції – це найменш

загальний тип, що, грубо кажучи, містить усі можливі “екземпляри” виразу чи функції.

Приклад 1. (Одне рівняння).

Параметричний поліморфізм (1/3)

swap(x, y) = (y, x)

Найменш загальний тип – тип функції swap

(t1,t2) -> (t3,t4)
(t1,t2) -> t3
t1 -> t2

Більш загальні типи

(2/3)
head1 (x:_) = x
head1 [] = error "List empty"
[t1]

-> t2
t1 -> t2

Більш загальні типи, ніж тип [t] -> t

Найменш загальний тип

Зіставлення зі зразком (pattern matching)

Та ж уніфікація!

поліморфізм, більш відомий як перевантаження (overloading).
Розглянемо лише один приклад для

розуміння проблеми. Оператор порівняння або рівності (==) зазвичай використовується із багатьма типами. Але, по-перше, не з усіма (оскільки, наприклад, порівняння функцій спряжене з алгоритмічно нерозв'язною проблемою) і, по-друге, порівняння, скажімо, двох списків чи дерев істотно відрізняється від порівняння двох чисел (саме тому природним є використання перевантаження оператора (==) для таких різноманітних порівнянь).
Використання спеціального поліморфізму (перевантаження) у мові Haskell спряжене із залученням так званих класів типів. Приклад.

Параметричний поліморфізм (2/2)

invers x = -x

Клас типів

Зіставлення зі зразком
head1 (x:_) = x
head1 []

= error "List empty"

Вже зустрічались із прикладами...

Зіставлення зі зразком (pattern matching)

Та ж уніфікація!

Кілька рівнянь

Wildcards (підстановкові символи)

“:” – інфіксний оператор, що додає перший аргумент як “голову” у початок списку, який визначається другим аргументом.
“:” – правоасоціативний оператор, тому вираз 1:(2:(3:[])) можна записувати як 1:2:3:[].
Скорочена форма для списків: замість 1:2:3:[] можна вживати [1,2,3].

tail (_:xs) = xs
tail [] = error " List empty "

-> a
last [x] = x
last (_:xs) = last

xs
last [] = error "List empty"

reverse0 y = reverse1 y []
reverse1 [] y = y
reverse1 (x:xs) y = reverse1 xs (x:y)

reverse1 [1,2,3] y

3:(2:(1:y))

Відомий прийом – використання допоміжної більш загальної функції.

Зверніть увагу на форму використання двох аргументів у reverse1 та особливості їх нотації (немає дужок, коми між аргументами).

-> ([a] -> [a])
?
Реальний тип reverse1. Тобто маємо унарну функцію,

яка відображає списки (типу [a]) у функції (типу [a]->[a] ).

З огляду на правоасоціативність “->” у мові Haskell

Такий підхід до тлумачення функцій саме і популяризував Haskell Curry.

Усі функції у мові Haskell роз-глядаються як каррінгові функції

reverse1 [] y = y
reverse1 (x:xs) y = reverse1 xs (x:y)

reverse1 [1,2,3] y

3:(2:(1:y))

Можна обмежитись одноаргументними функціями, спираючись на каррінг функцій.

Пригадаємо:

Вираз (функціонального) типу

“Часткове” обчислення

= y
reverse1 (x:xs) y = reverse1 xs (x:y)
[a] -> ([a]

-> [a])

reverse1 [1,2,3] y

3:(2:(1:y))

Реальний тип reverse1

Переконаємось у каррінговості reverse1, зокрема, спробуємо здійснити часткові обчислення:





Можна визначити нову функцію reverse1_1_2_3 на основі часткового обчислення:

reverse1_1_2_3 = reverse1 [1,2,3]

Зверніть увагу на круглі дужки

plus :: Integer -> Integer -> Integer
plus x

y = x + y

plus1 = plus 1

1)










2)

(Тип функції виводиться у Haskell!)

Double)

addVector :: Vector -> Vector -> Vector
addVector x y =

(fst x + fst y, snd x + snd y)

fst :: (a,b) -> a
fst (x,y) = x

snd :: (a,b) -> b
snd (x,y) = y

:: (a->b) -> [a] -> [b]
map1 f []

= []
map1 f (x:xs) = f x : map f xs

curry :: ((a, b) -> c) -> a -> b -> c
curry f x y = f (x, y)

uncurry :: (a -> b -> c) -> ((a, b) -> c)
uncurry f p = f (fst p) (snd p)

plus_pair = uncurry plus

Замість каррінгових функцій від двох аргументів іноді простіше мати справу з функцією над кортежною парою або ж, навпаки, замість одноаргументної функції від кортежної пари – мати справу із каррінговою функцією від двох аргументів

| x

= []
quicksort (x:xs) = quicksort [y | y <- xs, y ++ [x]
++ quicksort [y | y <- xs, y>=x]

fac 0 = 1
fac n = n * fac (n-1)

= []
| otherwise

= [x | x <- [1..num], num `mod` x == 0 ]

isPrime num
| num <= 1 = False
| otherwise = getDivisors num == [1,num]

allPrimeNumbers = filter isPrime [1..]

allPrimeNumbers1000000 = [y | y <- allPrimeNumbers, y>1000000]

main = take 1 allPrimeNumbers1000000

-> [a] -> [b] -> [c]
zipF _ []

[] = []
zipF f (x1:s1) (x2:s2) = (f x1 x2) : zipF f s1 s2

fib = 1 : zipF (+) fib (0 : fib)

goal = fib where
fib0 = 0:fib
fib1 = zipF (+) fib0 fib
fib = 1:fib1

zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip xs ys = []

fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]

команд (назви команд можна скорочувати до одного символа):
:quit;
:type;
:set - для

встановлення опцій інтерпретатора. Наприклад, :set +t (для виведення типу кожного обчисленого результату);
:set prompt > (змінюється вигляд запрошення).
:? - виводиться список можливих команд;
:load ... ;
:reload;
:edit.

The Glasgow Haskell Compiler