Модул 11. Функционално програмиране

Материали | Задачи | Решения | Видео

Съдържание

1. Въведение

2. Функции и стойности

3. Рекурсия

4. Списъци

5. Функции от по висок ред

6. Затваряне на състояние във функция

7. Подготовка за изпит

1. Въведение

Инсталация

1. Haskell

2. Microsoft Visual Studio Code

3. Haskell Syntax Highlighting Plugin

Първа програма

1. VS Code > File > New [Ctrl + N]

-- First Haskell Program
main = do
    putStrLn "Hello World"

1. VS Code > File > Save [Ctrl + S]

hello.hs

1. VS Code > Terminal > New terminal [Ctrl + Shift + `]

cd Desktop
ghc hello.hs
.\hello.hs

2. Функции и стойности

Деклариране на функция

square x = x * x

Функция с повече параметри

multMax a b x = (max a b) * x

Използване на скоби

(5 + 2) * (3 - 4) -- -7 
max (5 + 2) (sqrt 17) --  7
max 5 (-5) -- 5

Функции като стойности на функция

pass3 f = f 3
add1 x = x + 1 
pass3 add1
-- 4

Композиция

compose f g x = f (g x)
add1 x = x + 1
mult2 x = 2 * x

compose add1 mult2 4

Рекурсия

pow2 n =
	if n == 0
	then 1
	else 2 * (pow2 (n - 1))

3. Рекурсия

В Haskell няма цикли. Циклите се реализират чрез рекурсия. Итерациите се реализират с рекурсивни извиквания. Итераторите се реализират като параметри и се променят при всяко рекурсивно извикване.

Рекурсивна реализация на цикли

repeatString str n = 
    if n == 0
    then ""
    else str ++ (repeatString str (n-1))

За функциите, които зависят от външно състояние се използва помощна функция:

pow2loop n x i = 
    if i < n
    then pow2loop n (x*2) (i+1)
    else x
pow2 n = pow2loop n 1 0

Задача

Дефинирайте функция, която намира сбора на първите 10 естествени числа.

sumNumbers = sumNumbersLoop 0 1

sumNumbersLoop sum index = 
    if index > 10
    then sum
    else (sum + index) + (sumNumbersLoop sum (index + 1))

Опашкова рекурсия

Опашковата рекурсия е рекурсия, при която последното извършвано действие е рекурсивно извикване.

• Оптимизация на опашката = Tail Call Optimization

• Вместо с последващо връщане рекурсивното обръщение се реализира със преход без връщане

• При тази рекурсия заделената в стека памет се преизползва вместо да се заделя нова

• Намалява разхода на памет и обикновено подобрява бързината на алгоритъма, но по-трудно се откриват грешки

repeatStringLoop string result n = 
    if n == 0
    then result
    else repeatStringLoop string (result ++ string) (n - 1)

repeatString string n = repeatStringLoop string string n

4. Списъци

Инициализация на списък

x = [1,2,3]

Празен списък

empty = []

Операторът :

y = 0 : x -- [0,1,2,3]
x' = 1 : (2 : (3: [])) -- [1,2,3]

Символните низове също са списъци

str = "abcde"
str' = 'a' : 'b' : 'c' : 'd' : 'e' : []

Глава и опашка на списъци

Глава на списъка е първият елемент от него

head[1, 2, 3] -- 1

Опашка на списъка е всичко останало освен главата

tail [1,2,3] -- [2, 3]

В комбинация от функциите можем да достъпим следващия елемент от списъка

head (tail [1,2,3]) -- 2

Рекурсивно обхождане на списък

Рекурсивно обхождане на списък и умножаване на всяка стойност по 2:

doubleList list = 
    if null list
    then []
    else (2 * (head list) : (doubleList (tail list)))
	
doubleList [1,2,3,4,5] -- [2,4,6,8,10]

Функция, филтрираща елементите в списък (премахва нечетни числа):

removeOdd nums =
    if null nums
    then []
    else 
        if (mod (head nums) 2 ) == 0
        then (head nums) : (removeOdd (tail nums))
        else removeOdd (tail nums)

Дължина на списък

За намиране на дължината на списък се използва функцията length

length [1,2,3,4,5] -- 5

Собствена функция за намиране на дължината

listLength [] = 0
listLength list = findLength 1 list
findLength length list = 
    if null list
    then (length - 1)
    else findLength (length + 1) (tail list)

Създаване на списък чрез рекурсия

Създаване на списък чрез рекурсия:

createList start end = createListLoop [] start end
createListLoop list start end =
    if start > end
    then list
    else createListLoop (list ++ [start]) (start + 1) end
	
createList 1 10 -- [1,2,3,4,5,6,7,8,9,10]

Създаване на обърнат списък чрез рекурсия:

createReverseList start end = createReverseListLoop [] start end
createReverseListLoop list start end =
    if start > end
    then list
    else createReverseListLoop (start : list) (start + 1) end

createReverseList 1 10 -- [10,9,8,7,6,5,4,3,2,1]

В Haskell създаването на списък може да продължава до безкрайност:

intsFrom n = n : (intsFrom (n+1))
ints = intsFrom 1 -- Продължава до безкрайност

take 10 ints -- [1,2,3,4,5,6,7,8,9,10]

Задача

Дефинирайте функция, която приема списък и число n и връща като резултат n-тия елемент от списъка

nThElement list n = nThElementLoop list (length list) n 0
nThElement [] _ = error "Empty list" 
nThElementLoop list listLength n index =
    if n >= listLength || n < 0
    then error "Index outside bounds of array"
    else if index == n
         then (head list)
         else nThElementLoop (tail list) listLength n (index + 1)

5. Функции от по-висок ред

Абстракции чрез функции

• Ако функция a приема като параметри b, c и друга функция func и връща резултат извиканата функция func с параметри b и c, то резултатът всеки път ще е различен

• Резултатът зависи от подадената функция func, като единственото условие е тя да приема същия брой параметри, които и се подават в тялото на a

abstThroughFunction a b func = func a b
firstFunc a b = (a * b)
secondFunc a b = (a  + b)
thirdFunc a b = (a - b)

abstThroughFunction 10 10 firstFunc -- 100
abstThroughFunction 10 10 secondFunc -- 20
abstThroughFunction 10 10 thirdFunc -- 0

Изчисления върху списъци

Функцията map приема като параметри функция и списък и връща като резултат нов списък, като върху един елемент от първоначалният списък е извикана подадената функция.

absoluteList list = map abs list
absoluteList [1,2,-3,-4] -- [1,2,3,4]

plus1List list = map (1 + ) list
plus1List [1,2,3,4,5] -- [2,3,4,5,6]

Функцията filter тества всеки елемент от списък и връща само тези, които минават теста (функция, която връща тип boolean)

isEven x = x `mod` 2 == 0
removeOdd = filter isEven

removeOdd [1,2,3,4,5,6,7,8] -- [2,4,6,8]

Сгъване на списък е комбиниране на всички стойности от списъка в една. Има две вградени функции, които правят това:

• Функцията foldl = действията се извършват от ляво надясно

• Функцията foldr = действията се извършват от дясно наляво

И двете функции приемат три параметъра:

• Акумулатор - функцията, която ще се извиква между елементите на списъка

• Начална стойност, от която да започне изчислението

• Самият списък

И при двете функции изчисленията започват от стойността на акумулатора:

• foldl е по-бърза функция

• foldr намира приложението си при работа с безкрайни списъци

subtractList list = foldl (-) 0 list
subtractList' list = foldr (-) 0 list

subtractList [1,2,3,4,5] -- -15
subtractList' [1,2,3,4,5] -- 3

Функцията zip приема като аргументи два списъка и връща като резултат списък от двойки, където първият елемент е от първият списък, а другият от вторият списък.

zip [1,3,5] [2,4,6] -- [(1,2),(3,4),(5,6)]
zip [1,2] [3,4,5,6] -- [(1,3),(2,4)]
zip [] [1] -- []

Функцията zipWith освен два списъка приема и функция, която да използва при комбинирането на елементи от двата списъка.

zipWith (+) [1,2,3,4,5] [9,8,7,6,5] -- [10,10,10,10,10]

Задача

Дефинирайте функция, която приема лист и връща най-големият елемент от нея. Използвайте някоя от научените функции за изчисления върху списък.

maxFromList list = foldl max (head list) list
maxFromList [-1, 5, 10] -- 10

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

Следният синтаксис често обърква и прави кода нечетим

plus3 x y z = x + y + z

В такива случаи много удобни за използване са анонимните функции

(\x y z -> x + y + z)
(\x y z -> x + y + z) 10 20 30 -- 60

В Haskell е възможно и да се дават имена на анонимни функции, ако по някаква причина това е нужно

plus3' = (\ x y z -> x + y + z)

Анонимните функции имат огромно приложение при използването на вградените в Haskell функции map и foldl/foldr при работа със списъци

addOneList list = map (\x -> x + 1) list
addOneList [1,1,1] -- [2,2,2]

Задача

Използвайте вградената в Haskell функция zipWith, като за първи параметър (функция) използвате ваша анонимна функция, която връща сбора на два елемента.

zipWith (\ x y  -> x + y ) [10,12] [3,4] -- [13,16]

6. Затваряне на състояние във функция

• В Haskell съществуват функции с така наречените "свободни променливи" (променливи, които не са директно подадени като параметър на функцията)

• Функциите със свободни променливи наричаме функции с вътрешно състояние

• Haskell използва функции със свободни променливи почти навсякъде т.е. функциите с вътрешно състояние се използват навсякъде

Пример

f x = (\y -> x + y)

f връща функция с вътрешно състояние, защото променливата x, която е подадена отвън за анонимната функция, се използва вътре в дефиницията ѝ

Функциите с вътрешно състояние са обратния случай на комбинаторите - функции без свободни променливи.

Функция без свободни променливи е чиста анонимна функция, която се обръща само към своите аргументи.

 \a -> a
 \a -> \b -> a
 \f -> \a -> \b -> f b a

7. Подготовка за изпит

Задaчa. 1 Цифра като дума

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

Вход	Изход
0	Zero
1	One
2	Two
3	Three
4	Four
5	Five
6	Six
7	Seven
8	Eight
9	Nine

При въвеждане на End програмата да спира изпълнението си. За целта - възползвайте се от библиотеката System.Exit и метода, който тя предлага exitWith, като го извикате с параметър ExitSuccess. При вход на отрицателно число или число с повече от 1 цифра да се изпише: Please only enter single digit positive numbers.

Пример

Вход	Изход
5	Five
9	Nine
11	Please only enter single digit positive numbers
End

Задача 2. Средно аритметично на цифрите на число

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

• На стандартният вход се въвежда цяло число N

• На стандартният изход се извежда цяло число - средното аритметично на цифрите на N

Ограниения

1 <= N <= 10000

Пример

Вход	Изход
2222	2
2345	3

Задача 3. Най-малка цифра в число

Да се състави прогрма, която намира и отпечатва най-малката цифра в цяло число.

• На стандартният вход се въвежда цяло число N

• На стандартният изход се отпечатва цяло число M - най-малката цифра в N

Ограничения

1 <= N <= 10000

Пример

Вход	Изход
6798154	1