Wstęp do programowania funkcyjnego

Błażej Święcicki

Czym jest programowanie funkcyjne?

Czym jest Haskell?

Językiem programowania:

Podstawy Haskella

Definiowanie funkcji i ich typów:
fib :: Num a => a -> a
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

Listy

[1,2,3,4,5] :: Num a => [a]
1 : 2 : 3 : 4 : 5 : [] :: Num a => [a]
Obie notacje są równoznaczne
(:) :: a -> [a] -> [a]
Operator (:) dołącza element do początku listy
[1..5]
[1..]
Pierwsze wyrażenie tworzy listę od [1,2,3,4,5], drugie tworzy nieskończoną listę zaczynającą się od 1.
To nie jest magia – można zdefiniować funkcję która zwraca taką listę:
inflist n = n : inflist (n+1)

Funkcje wieloargumentowe

W wielu językach funkcyjnych nie ma funkcji wieloargumentowych. Jak więc zrealizować na przykład dodawanie?
(+) :: Num a => a -> a -> a
Dodawanie jest tak na prawdę funkcją, która zwraca funkcję, która zwraca liczbę. Dla przykładu:
(2 +) :: Num a => a -> a
2 + 2 :: Num a => a
(1 -) :: Num a => a -> a
(- 1) :: Num a => a -> a

Jak tworzyć takie funkcje?

dodaj a b = a + b
dodaj a = \b -> a + b
dodaj = \a -> \b -> a + b
dodaj = \a b -> a + b

Operacje na listach

map :: (a -> b) -> [a] -> [b]
Aplikuje funkcję do wszystkich elementów listy.
map _ [] = []
map f (x:xs) = f x : map f xs
filter :: (a -> Bool) -> [a] -> [b]
Zwraca elementy listy dla których predykat jest prawdziwy.
filter _ [] = []
filter p (x:xs) = if p x
                  then x : filter p xs
                  else filter p xs 

Operacje na listach

foldr :: (a -> b -> b) -> b -> [a] -> b
Redukuję listę od prawej do lewej.
foldr _ z []     =  z
foldr f z (x:xs) =  f x (foldr f z xs)
zip :: [a] -> [b] -> [(a,b)]
Zwraca listę par, z której każda ma n-ty element z pierwszej listy i n-ty z drugiej.

zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip _ _ = []
zipWith f xs ys = map (\(a,b) -> a b) (zip xs ys)

Inne funkcje

(x:xs) !! 0 = x
(x:xs) !! idx = xs !! (idx - 1)

take 0 _ = []
take _ [] = []
take n (x:xs) = x : take (n - 1) xs

flip f x y = f y x

f $ x = f x
f . g = \x -> f (g x)

fix f = f (fix f)

Pytania