-- Task 1
repeat1 :: Int -> a -> [a]
repeat1 0 x = []
repeat1 n x = x : repeat1 (n - 1) x

repeatAll :: Int -> [a] -> [a]
repeatAll 0 list = []
repeatAll n [] = []
repeatAll n (x : xs) = (repeat1 n x) ++ (repeatAll n xs)

-- Task 2
removeNth :: Int -> [a] -> [a]
removeNth n list = removeNth' n 1 list

removeNth' :: Int -> Int -> [a] -> [a]
removeNth' n cur_pos [] = []
removeNth' n cur_pos (x : xs)   | (mod cur_pos n) == 0 = removeNth' n (cur_pos + 1) xs
                                | otherwise = x : (removeNth' n (cur_pos + 1) xs)

-- Task 3
getSubList :: Int -> Int -> [a] -> [a]
getSubList n k [] = []
getSubList 0 0 (x : xs) = []
getSubList 0 k (x : xs) | k < 0 = error "bad bound"
                        | otherwise = x : (getSubList 0 (k - 1) xs)
getSubList n k (x : xs) = getSubList (n - 1) (k - 1) xs

-- Task 4
shift :: Int -> [a] -> [a]
shift n list    | n > 0 = reverse (shift (-n) (reverse list))
                | n == 0 = list
                | (-n) > length(list) = shift (-(mod (-n) (length list))) list
                | otherwise = (getLastN (-n) list) ++ (removeLastN (-n) list)

getLastN :: Int -> [a] -> [a]
getLastN n list | n < 0 = error "n < 0"
                | n >= length(list) = list
                | otherwise = getLastN n (tail list)

removeLastN :: Int -> [a] -> [a]
removeLastN n list  | n < 0 = error "n < 0"
                    | n >= length(list) = []
                    | otherwise = (head list) : (removeLastN n (tail list))

-- Task 5
remove :: Int -> [a] -> (a, [a])
remove n [] = error "element not found"
remove 0 (x : xs) = (x, xs)
remove n (x : xs)   | n < 0 = error "negative index"
                    | otherwise = (fst p, x : snd p)
                        where p = remove (n - 1) xs

-- Task 6
pushToAll :: a -> [[a]] -> [[a]]
pushToAll z [] = [[z]]
pushToAll z [x] = [z : x]
pushToAll z (x : xs) = (z : x) : (pushToAll z xs)

combinations :: Int -> [a] -> [[a]]
combinations n [] = []
combinations 0 list = []
combinations n (x : xs) | n < 0 = []
                        | n > length(x : xs) = []
                        | n == length(x : xs) = [x : xs]
                        | otherwise = (pushToAll x (combinations (n - 1) xs)) ++ (combinations n xs)

data Tree a = Empty | Branch (Tree a) a (Tree a) deriving (Show, Eq)
-- Task 7
allBalanced :: Int -> [Tree ()]
allBalanced 0 = [Empty]
allBalanced n   | n < 0 = []
                | otherwise = allBalanced' (div (n - 1) 2) ((n - 1) - (div (n - 1) 2))

allBalanced' :: Int -> Int -> [Tree ()]
allBalanced' left right | left < 0 || right < 0 = []
                        | left < (right - 1) = allBalanced' (left + 1) (right - 1)
                        | left > (right + 1) = []
                        | otherwise = (mergeLists (allBalanced left) (allBalanced right)) ++ (allBalanced' (left + 1) (right - 1))

mergeLists :: [Tree ()] -> [Tree ()] -> [Tree ()]
mergeLists [] list2 = []
mergeLists list1 [] = []
mergeLists (x : xs) list2 = (mergeTree x list2) ++ (mergeLists xs list2)

mergeTree :: Tree () -> [Tree ()] -> [Tree ()]
mergeTree tree [] = []
mergeTree tree (x : xs) = (Branch (tree) () (x)) : (mergeTree tree xs)

-- Task 8
buildTree :: [a] -> Tree a
buildTree [] = Empty
buildTree list = Branch (buildTree left) root (buildTree right)
                    where
                        (left, root, right) = split (div (length list) 2) list

split :: Int -> [a] -> ([a], a, [a])
split pos list = split' pos list 0 []

split' :: Int -> [a] -> Int -> [a] -> ([a], a, [a])
split' pos [] cur_pos left = error "root not found"
split' pos (x : xs) cur_pos reversed_left   | cur_pos == pos = (reverse reversed_left, x, xs)
                                            | otherwise = split' pos xs (cur_pos + 1) (x : reversed_left)

-- Task 9
allBalancedH :: Int -> [Tree ()]
allbalancedH 0 = [Empty]
allBalancedH n = allBalancedH' n 0

-- fix n
allBalancedH' :: Int -> Int -> [Tree ()]
allBalancedH' n h   | h > n - 1 = []
                    | otherwise = (allBalancedH'' n h) ++ (allBalancedH' n (h + 1))

-- fix n and h
allBalancedH'' :: Int -> Int -> [Tree ()]
allBalancedH'' 0 h  | h == (-1) = [Empty]
                    | otherwise = []
allBalancedH'' n h  | (h < 0) || (h > n - 1) = []
                    | otherwise = (allBalancedH''' 0 (n - 1) (h - 2) (h - 1)) ++ (allBalancedH''' 0 (n - 1) (h - 1) (h - 2)) ++ (allBalancedH''' 0 (n - 1) (h - 1) (h - 1))

-- fix left_h right_h
allBalancedH''' :: Int -> Int -> Int -> Int -> [Tree ()]
allBalancedH''' left_n right_n left_h right_h   | right_n < 0 = []
                                                | right_n == 0 = mergeLists (allBalancedH'' left_n left_h) (allBalancedH'' right_n right_h)
                                                | otherwise = (mergeLists (allBalancedH'' left_n left_h) (allBalancedH'' right_n right_h)) ++ (allBalancedH''' (left_n + 1) (right_n - 1) left_h right_h)