{-
	Упражнение №6 - рекурсивни програми за списъци
-}
module Exercise6 where
{-
	Метод на бързото сортиране:
	За да сортирате един списък, вземете първия му елемент x, и разделете
	остатъка от списъка на две части - елементите <=x и елементите >x. И двата
	списъка са по-малки от първоначалния, следователно можем да приложим
	рекурсия да ги сортираме. След това слепваме последователно елементите <=x,
	елемента x и елементите >x
-}
qsort :: Ord(a) => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort [ y | y <- xs, y <= x ] ++ [x] ++ qsort [ y | y <- xs, y > x]
{-
	Метод на сливането:
	За да сортирате един списък, разделете го на две приблизително еднакви части
	след което ги сортирайте рекурсивно и ги слейте.
	Ще решим задачата на три етапа
	I етап: разделете списък на две приблизително еднакво големи части
	Идея А: вземаме първата и втората половина на списъка
	Идея Б: "раздаваме" елементите по равно - един на мен, един на теб
-}
split1 :: [a] -> ([a],[a])
split1 l = (take n l, drop n l)
	where n = length l `div` 2
split :: [a] -> ([a],[a])
split [] = ([],[])
split [x] = ([x],[])
split (x:y:xs) = (x:l1,y:l2)
	where (l1,l2) = split xs
{-
	II етап: сливаме два подредени списъка
-}
merge :: Ord(a) => ([a],[a]) -> [a]
merge ([],l) = l
merge (l,[]) = l
merge (x:xs,y:ys)
	| x <= y	= x : merge (xs,y:ys)
	| otherwise	= y : merge (x:xs,ys)
{-
	III етап: сортирането
-}
mergeSort :: Ord(a) => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort l = merge (mergeSort l1, mergeSort l2)
	where (l1,l2) = split l
{-
	Напишете функция, която заменя всяко срещане на елемента x в списъка l
	със елемента y
	Първи вариант: list comprehension
-}
replace1 :: Eq(a) => a -> a -> [a] -> [a]
replace1 x y l = [ chooseFrom x y a | a <- l ]

chooseFrom :: Eq(a) => a -> a -> a -> a
chooseFrom x y a
	| x == a	= y
	| otherwise	= a
{-
	Втори вариант: рекурсивно
-}
replace2 :: Eq(a) => a -> a -> [a] -> [a]
replace2 x y [] = []
replace2 x y (a:xs)
	| x == a	= y : replace2 x y xs
	| otherwise	= a : replace2 x y xs
{-
	Напишете функция, която по дадени два списъка проверява дали първият списък
	е начало на втория. Например [1,2,3] е начало на [1,2,3,7,4,8]
-}
startsWith :: Eq(a) => [a] -> [a] -> Bool
startsWith [] l = True
startsWith (x:xs) [] = False
startsWith (x:xs) (y:ys)
	| x == y	= startsWith xs ys
	| otherwise	= False
{-
	Малко по-кратко решение
-}
startsWith2 [] l = True
startsWith2 (x:xs) [] = False
startsWith2 (x:xs) (y:ys) = x == y && startsWith2 xs ys