{--
T(n) = 2*T(n/2)+O(n) --> O(n*log(n))
Sortiranje se svodi na podelu liste na dva dela:
1) levog u kojem su svi elementi manji od pivota
2) desnog u kojem su svi elementi veci ili jednaki
od pivota

Potom se za 1) i 2) rekurzivno izvrsi sortiranje i onda
se sve spoji u redosledu 1), pivot, 2)
-}
qsortiraj [] = []
qsortiraj (x:xs) = (qsortiraj l)++[x]++(qsortiraj d) 
	where
		l = [y|y<-xs,y<x] 
		d = [y|y<-xs,y>=x]
		
{--
lambda izrazi su anonimne funkcije
notacija:

(\arg1 arg2 arg3... -> (f arg1,arg2,arg3,...))

\x->x+1

Main> (\x->x+1) 5
6
\x y->x+y

Main> (\x y->x+y) 5 5
10
-}

{--
Sta je zajednicko za funkcije:
1) koje povecavaju svaki element liste za 1
2) koje kvadriraju svaki element liste
3) mnoze svaki element sa 3 
itd.

Zajednicko je da sve imaju isto ponasanje:
1) prolazak kroz listu
2) primena neke transformacije nad svakim el. liste

Razlicita je:
1) Samo ta unarna transformacija (transformacija ne mora
da ima isti domen i kodomen npr. hocemo da 
za svaki element celobrojne liste izracunamo 
njegov koren [10,4,9,] -> [3..., 2, 3] 
-}
-- Dimenzija izlazne liste je ista kao i dim. ulazne
mapiraj :: (a->b)->[a]->[b]
mapiraj f [] = []
mapiraj f (x:xs) = (f x):(mapiraj f xs)

{--
Main> mapiraj (\x->x+1) [1,2,3,4,6]
[2,3,4,5,7]
Main> mapiraj (\x->x*x) [1,2,3,4,6]
[1,4,9,16,36]
Main> mapiraj reverse ["afds","bsdf","dfgd"]
["sdfa","fdsb","dgfd"]
-}

{--
Sta je zajednicko za funkcije:

1) Koje izbacuju sve neparne el. iz liste
2) Izbacuju sve koji nisu stepeni dvojke
3) Sve ciji zbir cifara ne prelazi 10

Zajednicko je:
1) Prolazi se kroz listu 
2) Pita se neka kriterijumska (unarna) funkcija
da li da se element zadrzi ili ne
-}
-- Dimenzija izl. liste je manja ili jednaka dim. 
-- ulazne liste
filtriraj :: (a->Bool)->[a]->[a]
filtriraj f [] = []
filtriraj f (x:xs) = if (f x) then x:fxs else fxs
				where
					fxs = (filtriraj f xs)
{--
Main> filtriraj (\x->x `mod` 2==0) [1,3,4,6,4,7,4453,45]
[4,6,4]
-}

{--
Sta je zajednicko za:

1) Sabiranje elemenata liste
2) Mnozenje el. liste
3) Spajanje liste reci u tekst
4) Eliminasnje unutrasnjih zagrada iz liste list
5) Duzina liste
itd. 

Zajednicko je:
1) Primenjujemo nekakvo "spajanje" (agregacija) 
izmedju elemenata liste

Specificno je:
1) Sta je spajanje (sabiranje, mnozenje, konkatenacija...)
2) Neutral za operaciju spajanja, odnosno sta se vraca
u situaciji kada je lista prazna (za sabiranje je 0, 
za mnozenje 1, za spajanje stringova prazna lista itd.)
-}

spoji1 :: (a->b->b)->b->[a]->b
spoji1 f e [] = e
spoji1 f e (x:xs) = f x (spoji1 f e xs)

{-- primer za sabiranje  
Main> spoji1 (\x y->x+y) 0 [1,2,3,5]
11

spoji1 f 0 [1,2,3,5] --> x=1 xs=[2,3,5]
f 1 (spoji1 f 0 [2,3,5]) --> x=2 xs=[3,5]
f 1 (f 2 (spoji1 f 0 [3,5])) -->  x=3 xs=[5]
f 1 (f 2 (f 3 spoji1 f 0 [5])) --> x=5 xs=[]
f 1 (f 2 (f 3 (f 5 (spoji1 f 0 [])))) -->
f 1 (f 2 (f 3 (f 5 0))) -->
f 1 (f 2 (f 3 5))
f 1 (f 2 8)
f 1 10
11 
-}

{--
Primer nad spajanjem listi:
Main> "fdsfd"++"fdsafds"
"fdsfdfdsafds"
Main> spoji1 (++) "" ["fds","fdsxa","aaa"]
"fdsfdsxaaaa"
Main> spoji1 (++) "" [[1,2,3],[3,5,43]]
ERROR - Cannot infer instance
*** Instance   : Num Char
*** Expression : spoji1 (++) "" [[1,2,3],[3,5,43]]

Main> spoji1 (++) [] [[1,2,3],[3,5,43]]
[1,2,3,3,5,43]
-}

{--
spoji1 je memorijski zahtevnija implementacija
sazimanja jer joj raste stek: zato sto svaki rekurzivni
poziv se svodi na sledeci i izracunavanje konacnog
rezultata se izvrsava tek na kraju. 

Main> spoji1 (+) 0 [1..10000]
50005000
Main> spoji1 (+) 0 [1..10000000]
ERROR - C stack overflow

--}

saberip [] a = a
saberip (x:xs) a = saberip xs a+x

spoji2 f a [] = a
spoji2 f a (x:xs) = spoji2 f (f x a) xs

{-- ova varijanta
funkcije spoji je efikasnija jer koristi konstantan
stek (memorijski je jeftinija

Main> spoji2 (+) 0 [1,2,3,54]
60
-}

{--
Nazivi ugradjenih funkcija:
mapiraj -> map
filtriraj -> filter
spoji1 -> foldr
spoji2 -> foldl
-}

{- zad2

Main> map (\x->x++[(foldr (+) 0 x)]) [[1,2,3],[4,5,6],[]]
[[1,2,3,6],[4,5,6,15],[0]]

-}

{- zad3

Main> foldr (++) [] [[1,2,3],[4,5,6],[]]
[1,2,3,4,5,6]

-}

{- zad4
kod fold-a u x se nalazi glava a u y se nalazi resenje za rep
foldr (\x y->if (y==[] || x/=(head y)) then x:y else y) [] [1,1,2,3,4,3,3,4,4,5,5,5,5,3]
[1,2,3,4,3,4,5,3]
-}

{- zad5
foldr (\(x,y) (p,q)-> (x:p,y:q)) ([],[]) [(1,2),(3,4),(5,6)]
([1,3,5],[2,4,6])
-}