-- University of Zagreb
-- Faculty of Electrical Engineering and Computing
--
-- PROGRAMMING IN HASKELL
--
-- Academic Year 2013/2014

-- The following are some *example* solutions to the 4th homework
-- assignment. You were not required to write them out exactly like
-- this. If you spot an error somewhere, please notify us. Thanks!

module Homework where

import Data.Char
import Data.List

-- 1a
map' :: (a -> b) -> [a] -> [b]
map' _ []     = []
map' f (x:xs) = f x : map' f xs

-- 1b
filter' :: (a -> Bool) -> [a] -> [a]
filter' _ []     = []
filter' p (x:xs) = if p x then x : filter' p xs else filter' p xs

-- 1c
iterate' :: (a -> a) -> a -> [a]
iterate' f x = let y = f x in y : iterate' f y

-- 1d
intercalate' :: [a] -> [[a]] -> [a]
intercalate' _ []     = []
intercalate' _ (x:[]) = x
intercalate' d (x:xs) = x ++ d ++ intercalate' d xs

-- 2
sumEvens :: Num a => [a] -> a
sumEvens = sum' 0 (0 :: Int)
  where
    sum' s _ [] = s
    sum' s i (x:xs) = let s' = if even i then s+x else s
                      in  sum' s' (i+1) xs

-- 3
dup :: [a] -> [a]
dup = dup' 1
  where
    dup' _ []     = []
    dup' n (x:xs) = replicate n x ++ dup' (n+1) xs

-- 4
prime :: Integral a => a -> Bool
prime 1 = True
prime n = prime' $ n-1
  where
    prime' 1 = True
    prime' i = n `mod` i /= 0 && prime' (i-1)

-- 5
words' :: String -> [String]
words' = step []
  where
    step [] []     = []
    step cs []     = [cs]
    step cs (x:xs)
      | isSpace x = if null cs then step [] xs else reverse cs : step [] xs
      | otherwise = step (x:cs) xs

-- 6
prefixCalculator :: String -> Double
prefixCalculator [] = 0
prefixCalculator cs = read . head . foldr calc [] $ words cs
  where
    calc "+" (x:y:xs) = show (d x + d y) : xs
    calc "-" (x:y:xs) = show (d x - d y) : xs
    calc "*" (x:y:xs) = show (d x * d y) : xs
    calc "/" (x:y:xs)
      | d y == 0      = error "Division with zero"
      | otherwise     = show (d x / d y) : xs
    calc x xs         = x:xs

    d :: String -> Double
    d = read

-- 7
findSubsequence :: (Eq a) => [a] -> [a] -> [Int]
findSubsequence subSeq s = find' subSeq s 0
  where
    find' [] _ _ = []
    find' _ [] _ = error "Subsequence does not exist."
    find' (x:xs) (y:ys) idx
      | x == y    = idx : find' xs ys (idx+1)
      | otherwise = find' (x:xs) ys $ idx+1

-- 8a
nubRight :: Eq a => [a] -> [a]
nubRight = reverse . foldl (\s x -> if x `elem` s then s else x:s) []

-- 8b
nubLeft :: Eq a => [a] -> [a]
nubLeft []     = []
nubLeft (x:xs) = if x `elem` xs then nubLeft xs else x : nubLeft xs

-- 9
median :: (Integral a, Fractional b) => [a] -> b
median [] = 0
median xs = let ds = map realToFrac xs in med ds ds
  where
    med (a:_)   [_]      = a
    med (a:b:_) [_,_]    = (a+b) / 2
    med (_:as)  (_:_:bs) = med as bs

-- 10
type Vertex = Integer
type Graph  = [(Vertex,Vertex)]

-- 10a
getNbrs :: Graph -> Vertex -> [Vertex]
getNbrs g v = [if a == v then b else a | (a,b) <- g, a == v || b == v]

isNbrWith :: Graph -> Vertex -> Vertex -> Bool
isNbrWith g a b = a `elem` getNbrs g b

-- 10b
areConnected :: Graph -> Vertex -> Vertex -> Bool
areConnected gr v1 v2 = areConn gr v1 v2 [v1]

areConn :: Graph -> Vertex -> Vertex -> [Vertex] -> Bool
areConn g a b visited = isNbrWith g a b || testNbrs (getNbrs g a \\ visited)
  where
    testNbrs [] = False
    testNbrs (n:ns) = areConn g n b (visited ++ [n]) || testNbrs ns