{-
	Упражнение №5 - примитивно рекурсивни програми за списъци
-}
module Exercise5 where
{-
	Списъци могат да се конструират по много начини:
	[1,2,3]
	[1..10]
	[ x | x <- [1..10], prime x]
	За Хаскел обаче всички списъци могат да изглеждат по два начина:
	l = [] - празен списък
	l = x:xs, където елементът x е глава, а списъкът xs е опашка на l
	Списъци се залепят с помощта на оператора ++
	С помощта на == проверете, че [1..3], [1,2,3], [1]++[2]++[3] и 1:2:3:[]
	са еднакви списъци
-}
isOneTwoThree l = [1,2,3] == l
isThisTrue = isOneTwoThree [1..3] &&
             isOneTwoThree ([1]++[2]++[3]) &&
             isOneTwoThree (1:2:3:[])
{-
	Напишете функция ocurrences x l, която намира броя на срещанията на
	x в списъка l
-}
occurrences :: Eq(a) => a -> [a] -> Int
{-
	Това горе е типът на програмата.
	Чете се по следния начин: 
	"Eq(a) =>" значи, че a е тип, елементите на който могат да се сравняват с ==
	"a ->" значи, че първият аргумент на occurrences е елемент от тип a
	"[a] ->" значи, че вторият аргумент на occurrences е списък с елементи от тип a
	"Int" значи, че резултатът е цяло число
-}
occurrences x [] = 0
occurrences x (y:ys)
	| x == y	= i + 1
	| otherwise	= i
		where i = occurrences x ys
{-
	Примитивно-рекурсивните задачи често следват следния шаблон
	problem ... [] = ?
	problem ... (x:xs)
		| ?			= ?
		| otherwise	= ?
			where i = problem ... xs
	За да решите конкретната задача просто трябва да попълните четирите
	въпросителни.
-}
{-
	Напишете функция different l, която проверява дали списъкът l се състои
	от различни елементи
-}
different :: Eq(a) => [a] -> Bool
different [] = True
different (x:xs)
	| elem x xs	= False
	| otherwise	= different xs
{-
	Напишете функция removeDupl l, която получава списък, който съдържа всички
	елементи на l, но само по един път, т.е. премахва повторенията от l
-}
removeDupl :: Eq(a) => [a] -> [a]
removeDupl [] = []
removeDupl (x:xs)
	| elem x xs	= removeDupl xs
	| otherwise	= x:removeDupl xs
{-
	Напишете функции union, intersect, difference, която пресмята обединението,
	сечението и разликата на два списъка, в които елементите не се повтарят
-}
union :: Eq(a) => [a] -> [a] -> [a]
union [] l = l
union (x:xs) l
	| elem x l	= union xs l
	| otherwise	= x:union xs l

intersect :: Eq(a) => [a] -> [a] -> [a]
intersect [] l = []
intersect (x:xs) l
	| elem x l	= x:intersect xs l
	| otherwise	= intersect xs l

difference :: Eq(a) => [a] -> [a] -> [a]
difference [] l = []
difference (x:xs) l
	| elem x l	= difference xs l
	| otherwise	= x:difference xs l
{-
	Забележете колко е малка разликата между горните функции!
	Опитайте се да ги напишете с list comprehension

	Напишете функция ordered l, която проверява дали списък от числа е подреден
	във възходящ ред
	Първи вариант:
-}
orderedSlow :: Ord(a) => [a] -> Bool
orderedSlow [] = True
orderedSlow (x:xs)
	| lessThanAll x xs	= orderedSlow xs
	| otherwise			= False

lessThanAll x [] = True
lessThanAll x (y:ys)
	| x <= y	= lessThanAll x ys
	| otherwise = False
{-
	Втори вариант:
-}
orderedFast [x] = True
orderedFast (x:y:ys)
	| x <= y	= orderedFast (y:ys)
	| otherwise	= False
{-
	Пробвайте
	orderedSlow [1..5000]
	orderedFast [1..5000]
	Защо първата програма е по-бавна от втората?
	Ето още един вариант. На коя от горните програми съответства?
-}
ordered [x] = True
ordered (x:y:ys) = x <= y && ordered (y:ys)