module Lab10a where

nonGeneric :: [Int] -> [Int]
nonGeneric _ = [1, 2, 3]

generic :: [a] -> [a]
generic xs = take 4 xs

interleave :: a -> [a] -> [[a]]
interleave x []       = [[x]]
interleave x (y : ys) = (x : y : ys) : fmap (y :) (interleave x ys)

permutations :: [a] -> [[a]]
permutations []       = [[]]
permutations (x : xs) = concat $ fmap (interleave x) (permutations xs)

type Edge a = (a, a)
data Graph a = Graph
  { vertices :: [a]
  , edges    :: [Edge a]
  }
  deriving Show

gr :: Graph Int
gr = Graph { vertices = [1 .. 6]
           , edges    = [(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)]
           }

isPath :: Eq a => [Edge a] -> [a] -> Bool
isPath edges (x : y : xs) =
  ((x, y) `elem` edges || (y, x) `elem` edges) && isPath edges (y : xs)
isPath _ _ = True

isEdge :: Eq a => [Edge a] -> Edge a -> Bool
isEdge edges (x, y) = (x, y) `elem` edges || (y, x) `elem` edges

isPath' :: Eq a => [Edge a] -> [a] -> Bool
isPath' edges vs = all (isEdge edges) $ zip vs (tail vs)

findHamiltonian :: Eq a => Graph a -> [[a]]
findHamiltonian g = filter (isPath' (edges g)) $ permutations (vertices g)

data DualNum a = Dn a a
  deriving (Eq, Ord)

instance Show a => Show (DualNum a) where
  show (Dn x x') = show x ++ " + " ++ show x' ++ "eps"

instance Num a => Num (DualNum a) where
  (Dn x x') + (Dn y y') = Dn (x + y) (x' + y')
  (Dn x x') * (Dn y y') = Dn (x * y) (x' * y + x * y')
  (Dn x x') - (Dn y y') = Dn (x - y) (x' - y')
  abs (Dn x x') = Dn (abs x) (signum x * x')
  signum (Dn x x') = Dn (signum x) 0
  fromInteger i = Dn (fromInteger i) 0

f :: Num a => a -> a
f x = 13 * x ^ 3 + 2 * x + 5

instance Fractional a => Fractional (DualNum a) where
  fromRational r = Dn (fromRational r) 0
  (Dn x x') / (Dn y y') = Dn (x / y) ((x' * y - x * y') / (y * y))

sqr :: (Fractional a, Ord a) => a -> a
sqr x = convAbs $ iterate improve 1
 where
  improve r = (r + x / r) / 2
  convAbs (x1 : x2 : xs) | abs (x1 - x2) < 1e-10 = x2
                         | otherwise             = convAbs xs
  convAbs _ = error "End of infinite list"