haskell

www.kernel.org
apt-get install libncurses5-dev
make menuconfig (/usr/src/linux...)
sudo su (pass: student)

:::::::::::::::::::::::::::::::::::::::::::::::::::::
LEKCIQ 1:

boykobb@gmail.com

f (g x)
=> h = f . g
=> за всяко подходящо x: h x = f (g x)

x + y
=> (+) x y

((^2).(3*)) 5  => 5 * 3 = 15  =>  15 ^2 = 225

[[Int]] - spisyk ot spisyci ot celi chisla
Float
Double
Char

argument -> rezultat
pr: Int -> [Int]

map: prilaga deistvie F vyrhu vseki element ot spisyk S
(a -> b ) -> ( [a] -> [b] )

pr: f = map (^2)
    f [2,3,5] ___________ [4,9,25]
(map (^2)) [2,3,5]

УПР:
as = [4,1,0,3]
a' = map (^2) as
as'' = map (2^) as
bs = "abcd"
f x = [x,x]
bs' = map f bs

http://www.math.bas.bg/bantchev/teaching/
otvarqme test.hs -> tools -> go (f5)
:R - komanda reload

:::::::::::::::::::::::::::::::::::::::::::::::::::::
LEKCIQ 4


ns = f 1
 where f k = k : f (k+1)
  <=> това горе е евивалентно на:
ns = 1 : map (1+) ns


!!! map (има 2 случая)
1сл. за празен списък
2сл. за непразен списък

пр:
ns  = 1 : map (1+) ns
    = 1 : map (1+) (1 : map (1+) ns)
    = 1 : (1+) 1 : map (1+) (map (1+) ns)
    = 1 : 2 : ...
    = 1 : 2 : 3 : ...


!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1. ns = 1 : map (1+) ns
_____________________________
2. map_[] = []
3. map f (x:xs) = fx : map f xs
_____________________________
4. take 0 _= []
5. take _ []= []
6. take n (x:xs) = x:take(n-1)xs

legenda:
"_" -  nezawisimo kakyw broj elementi
"[]" - prazeb spisyk
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

           take 4 (map (^2) ns) =
[ot 1.]  = take 4 (map (^2) (1: map (1+) ns)) =
[ot 3.]  = take 4 ((^2) 1: map(^2)(map (1+) ns)) =
[ot 6.]  = (^2) 1: take (4-1)(map(^2)(map (1+) ns)) =
[ot 1.]  = 1: take 3 (map(^2) (map (1+) (1: map (1+) ns))) =
...      = 1: take 3 (map(^2) ((1+)1: map (1+) (map (1+) ns))) =
         = 1: take 3 ((^2)((1+)1) : map (^2) (map (1+)(map (1+) ns))) =
         = 1:(^2)((1+)1) : take (3-1)(map (^2) (map (1+)(map (1+) ns))) =
         = 1: 4 : take 2(map (^2) (map (1+)(map (1+) (1: map (1+) ns)))) =
         = 1: 4 : take 2(map (^2) (map (1+)((1+)1 : map(1+) (1: map (1+) ns)))) =
         = 1: 4 : take 2(map (^2) ((1+)((1+)1) : map(1+) (map(1+) (1: map (1+) ns)))) =
         = 1: 4 : take 2((^2) ((1+)((1+)1)) : map(^2) (map(1+) (map(1+) (1: map (1+) ns)))) =
         = 1: 4 : (^2) ((1+)((1+)1)) : take (2-1) (map(^2) (map(1+) (map(1+) (1: map (1+) ns)))) =
         = 1: 4 : 9 : take 1 (map(^2) (map(1+) ((1+)1 : map(1+)( map(1+) ns)))) =
         = 1: 4 : 9 : take 1 (map(^2) (((1+)((1+)1)) : map (1+) (map(1+)( map(1+) ns)))) =
         = 1: 4 : 9 : take 1 ((^2)((1+)((1+)1)) : map(^2)(map(1+)(map(1+)( map(1+) ns)))) =
         = 1: 4 : 9 : (^2)((1+)((1+)1)) : take (1-1) ( map(^2)(map(1+)(map(1+)( map(1+) ns)))) =
!!!! gubi se edna (1+) obyrkahme reshenieto 3-4 reda po-nagore
         = 1: 4 : 9 : 16 : []
         = [1, 4 ,9 , 16]

:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
LEKCIQ 5

unique [] = []
unique [x] = [x]
unique (x1:x2:xs) = if (x1 == x2) then unique ( x2:xs ) else x1 : unique ( x2:xs )

:: lokalno opredelenie (WHERE/LET)
1) UNIQUE(X1:X2:XS) = IF (X1 == X2) THEN RS ELSE X1:RS
     WHERE RS = UNIQUE (X2:XS)

2) UNIQUE XS = XS
____________________________________________________________________________________

length - returns array length (function from huskell standard library)

len [] = 0
len (x:xs) = 1 + len xs - edno plus dyljinata na ostatyka

len "abc" = 1 + len "bc" = 1 + ( 1 + len "c" ) =
= 1 + ( 1 + ( 1 + len " " )) = 1 + ( 1 + ( 1 + 0 ) ) = 3
____________________________________________________________________________________

reverse - "abcde" -> "edcba" (HSL)

rev1 [] = []
rev1 (x:xs) = rev1 xs ++ [x] // ++ dobavq spisyk ---> mnogo operacii n^2
_________________________________________________________________

("abcd", "") ->
('a':'b':'c':'d':[],[]) ->
('b':'c':'d':[],'a':[]) ->
('c':'d':[],'b':'a':[]) ->
('d':[],'c':'b':'a':[]) ->
([],'d':'c':'b':'a':[]) ->

rev2 xs = rv (xs,[])
    where rv([],bs) = bs
          rv(a:as,bs) = rv(as,a:bs)
__________________________________________________________________
x1,x2....xn-1, xn ->
x1,xn,x2,xn-1,.....

shuttle [] = []
shuttle (x:xs) = x: shuttle(reverse xs)


:::::::::::::::::::::::::::::::::::::::::::::::::::::
LEKCIQ 6

Функция за ляво групиране (foldr (right))
fr _ u [] = u
fr f u (x:xs) = f x (fr f u xs)
_____________________________________________________

Функция за дясно групиране (foldl (left))
fl _ u [] = u
fl f u (x:xs) = fl f (f u x) xs
_____________________________________________________

sum     = foldl (+) 0 = foldr (+) 0

product = foldl (*) 1 = foldr (*) 0

length xs = foldl f 0 xs
    where f s _ = s+1

map f xs = foldr g [] xs
    where g x rs = f x : rs
( fx1 : fx2 : ..... : fxn-1 : fxn : [] )

____________________________________________________________

reverse xs = foldl f u xs               reverse xs = foldl f [] xs
  where f rs x = x:rs        <=>        where f rs x = x:rs
    u = []


::::::::::::::::::::::::::::::::::::::::::::::::::::::
\a b -> a+b
тази ф-я обаче не е особено полезна
а тази е по-добра  \a b ->a+5*b това е функционален израз и може да се използва навсякъде
запис от този вид, както и при функциите с ... за удобство заисваме
\a -> (\b->...)
\(p,q) -> ... казва ме, че елемента на функцията е двойка (p,q)
ако вторият елемент не ни интересува може да напишем черта или конструктор т.е. \(p,_)-> или \(z:zs)->..
length = foldl (\   )
length = foldl(\n -> n+1)
фунции от стандартната библиотека - take, drop, map, filter, length, reverse...
foldl - имаме ф-я начална стойност и списък
foldr
да разбера какви са разликите м/у двете
каъв е резултатът от прилагане на fold l  на отделен числов списък foldl (-) 0 xs
и същият въпрос за foldr (-) 0 xs
0-x1, -x2, -x3,... -xn ...
= 0-(x1+x2+x3..+xn)
= сбора с отрицателен знак
= - (x1 +x2+....+xn)
вместо да пишем всичко това имаме фукнцията sum
= - (sum xs)
решение на вторят случай foldr (-) 0 xs
x1-(x2-(x3..-(xn-1-(xn -0)..)..)..) =
правим проверка за n =1; x1-0 = x1
за n=2; x1-(x2-0) = x1-x2
за n=3; x1-(x2-(x3-0)) = x1-x2+x3
за n=4; x1-(x2-(x3-(x4-0)))= x1-x2+x3-x4
извод: x1 винаги с полоителен знак, x2 винаги с отрицателен знак, тоест имаме редуване +, -, +, -, последниат знак се определя според четността
задача: функция за изчисляване дължината на списък
f xs = fold r (    ) - xs
какво трябва на пишем в скобите ?
лвият е поредниат елемент от списъка, а десния е натрупваната стойност
f xs = foldr (\-n ->n+1) - xs
за foldl (\n+1 -> -n) - xs , тоест разменят си местата
задача: да напишем функция за ресмятане на полином
1. създаваме списък с полиномите [C0, C1, ....Cn] - колкото е броят на числата в списъка -1, получаваме степента на полинома
кой е полинома [1,0,7] отг. x на втора степен +7

<<< 2. търсм по-удобна формула
(..((c0.x+c1).x+c2).x+....+Cn-1) .x+Cn
умножаваме с x и прибавяме следващиат елемент от списъка т.е. fldl , но н съвсем
c0 e добре да го заменим с 0
=> (...(((0.x + c0).x+c1) . x+c2) .x+...+cn-1).x+cn
вече сме готови да напишем функцията poly
poly cs x = foldl ( коя е функцията в скобите  ) 0 cs
poly cs x = foldl ( \ v c -> v.x+c ) 0 cs


::::::::::::::::::::::::::::::::::::::::::::::::::::::


fs - spisyk [f1, f2, ....]
x - stoinost

map_custom x fs = map ($x) fs           ....... f1 x, f2 x, ....
map_custom x = map ($x)

($x) = (flip ($)) x          flip f x y = f y x - smenq argumentite na funkciqta
((flip ($)) x) f = f x

=> map ($x) = map  (flip ($) x)
            = (map.flip ($)) x - kompozirana funkciq. 1wo deistw map, sledwana ot flip

=>  map_custom x = (map.flip($)) x
    map_custom = map.flip($)  <=>   map_custom x fs = map ($x) fs

    ____________________________________________

f x y    <=>   x 'f' y

f'(x,y)

g y = f'(x,y)  | Neudobno re6enie
h x = f'(x,y)  |

curry f x y = f (x,y)  - funkciq koqto razlaga dvoika, na 2 otdelni chlena

ex:  sbor(a,b) = a+b
    curry sbor 5 12 = 17

uncurry g (x,y) = g x y  - obratnoto na curry

    _____________________________________________

    a1, a2, ...
    b1, b2, ...
    zipWith - deistwa wyrhu 2 spisyka

zipWith f as bs
zipWith f as [] = []   <=>   zipWith _ _ [] = []
zipWith f [] bs = []         zipWith _ [] _ = []
zipWith f (a.as) (b.bs)  = f a b : zipWith as bs    - pone edin element

ex: zipWith (+) (1,2,3)(1,2,3)  = (2,4,6)

    (,) - operaciq za obrazwane na dwoika (a,b)

zip as bs = zipWith (,) as bs   <=>     zip = zipWith (,) - bezargumenten stil

zip3, zip4, ... zip7 - deistwat wyrhu powe4e ot 2 spisyka ... 3, 4, 5... 7
zipWith3, zipWith4, .... zipWith7
import Data.List     - za da vklu4im dopylnitelent modul

unzip - razdelq spisyl ot dvoiki na dvoika ot spisyci
unzip [] = ([],[])
upzip (x,y):xys = (x:xs, y:ys)
    where (xs,ys) = unzip xys

    _____________________________________________
fibs      = 0 1 1 2 3 5 8 12 21 34 55 .... redicata na fibonchi
tail fibs = 1 1 2 3 5 8 12 21 34 55 89 ....

fibs = 0:1:zipWith(+) fibs (tail fibs)

head - pyrwiq element
head (x:xs) = x

tail - wsi4ki elementi bez 1viq
tail (x:xs) = xs

last - posledniq element
last [x] = x
last (x:x1:xs) = last (x1:xs)

init - dawa vsi4ki elementi bez posledniq




:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::



type име на променлива [параметри] = израз описващ тип

пр:
type N = Int
type Coord = (Int,Int)
type Coord a = (a,a)
=> Coord Int - slojno ime na tipa
type Pair a b = (a,b)
type Table a b = [(a,b)]
type Graph a = [(a,[a])] <или> Table a [a]

_____________________________________________________

data име на тип [параметри] = Конструктор 1 | Констр. 2 | .....

пр:
data List a = Elist | Clist a (List a)
                аналогичен на:
                []          :
List Int
List (a->a)
Clist 'z' ( Clist ';' Elist )   -  списък от 2 елемента: 'z':';':[]  <или> ['z',';'] <или>  "z;"

listlen Elist = 0
listlen (Clist _ xs) = 1 + listlen xs

_______________________________________________________

Тип за представяне на двоично дърво:

data BinaryTree a = EmptyTree | CTree a (BinaryTree a) (BinaryTree a)
-> EmptyTree
-> CTree "abz" EmptyTree EmptyTree

Функция за обхождане Ляв - Корен - Десен:

BTreeWalk :: BinaryTree a -> [a]
BTreeWalk EmptyTree = []
BTreeWalk (Ctree x leftT rightT) = BTreeWalk leftT ++ [x] ++ BTreeWalk rightT

функция за построяване на двоично подреждащо дърво:
Ord - семейстовто (класа) на подредимите типове в хаскел

ListToBSTree :: Ord a => [a] -> BTree a
InsBSTree :: Ord a => а -> BTree a -> BTree a
InsBSTree x EmptyTree = CTree x EmptyTree EmptyTree
InsBSTree x (CTree y leftT rightT) =
    | x <= y | = CTree y (InsBSTree x leftT) rightT
    | x > y | = CTree y leftT (InsBSTree x rightT)

=> ListToBSTree = foldr InsBSTree EmptyTree

BSTreeSort = BinaryTreeWalk.ListToBSTree