-- | First assignment for IB016, semester spring 2016
--
-- You can use any modules from the @Base@ package if you wish.
-- However, try not to use list indexing,
-- i.e. do not use the function '!!'.
--
-- Name: Name Surname
-- UID: 123456

module Matrix (
    -- * Matrix type
      Matrix (..)
    -- * Printing
    , pprint
    -- * Properties
    , valid
    , dimensions
    , square
    -- * Manipulation and identity
    , diagonal
    , transpose
    , identity
    -- * Numerical operations
    , scalarMultiply
    , add
    , subtract'
    , multiply
    -- * Bonus
    , determinant
    ) where

import qualified Data.List as L ( transpose, splitAt )

-- | Matrix is represented as a list of rows of elements.
newtype Matrix a = Matrix { unMatrix :: [[a]] } deriving ( Show, Eq )

-- | Check if 'Matrix' is valid, it is valid if all rows have the same size.
--
-- >>> valid (Matrix [[1,2,2], [3,0,4]])
-- True
--
-- >>> valid (Matrix [[1,2], [3,4,0]])
-- False
valid :: Matrix a -> Bool
valid (Matrix m) = and $ zipWith (==) ls (tail ls)
  where
    ls = map length m

-- | Check if the given 'valid' 'Matrix' is a square matrix.
--
-- >>> square (Matrix [[1,2,2], [3,0,4]])
-- False
--
-- >>> square (Matrix [[1,2], [3,0]])
-- True
square :: Matrix a -> Bool
square = uncurry (==) . dimensions

-- | Return dimensions (number of rows, length of rows) of a 'valid' 'Matrix'.
--
-- >>> dimensions (Matrix [[1,2,2], [3,0,4]])
-- (2, 3)
dimensions :: Matrix a -> (Int, Int)
dimensions (Matrix []) = (0, 0)
dimensions (Matrix m) = (length m, length (head m))

-- | Return a diagonal of a given 'valid' 'Matrix' if it is 'square' matrix, or
-- 'Nothing' otherwise.
--
-- >>> diagonal (Matrix [[1,2,2], [0,3,4], [0,0,0]])
-- Just [1, 3, 0]
--
-- >>> diagonal (Matrix [[1,2,2], [3,0,4]])
-- Nothing
diagonal :: Matrix a -> Maybe [a]
diagonal mx@(Matrix m)
  | square mx = Just . map head . zipWith drop [0..] $ m
  | otherwise = Nothing

-- | Transpose a 'valid' matrix.
--
-- >>> transpose (Matrix [[1,2], [3,4]])
-- Matrix [[1,3], [2,4]]
--
-- >>> transpose (identity 3) == identity 3
-- True
transpose :: Matrix a -> Matrix a
transpose = Matrix . L.transpose . unMatrix

-- | For given dimension, return a square identity 'Matrix'.
--
-- >>> identity 4
-- Matrix [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]
identity :: Num a => Int -> Matrix a
identity dim = Matrix . take dim . map (take dim) $ [ ith i | i <- [0..] ]
  where
    ith :: Num a => Int -> [a]
    ith 0 = 1 : repeat 0
    ith i = 0 : ith (i - 1)

-- | Multiply a 'Matrix' with a scalar. Matrices are expected to be 'valid'.
--
-- >>> scalarMultiply 3 (Matrix [[1,2], [3,4]])
-- Matrix [[3,6], [9,12]]
scalarMultiply :: Num a => a -> Matrix a -> Matrix a
scalarMultiply x (Matrix m) = Matrix $ map (map (x *)) m

-- | Add two matrices if they can be added, return 'Nothing' otherwise.
-- Matrices are expected to be 'valid'.
--
-- >>> add (Matrix [[1,2], [3,4]]) (Matrix [[1,0], [0,1]])
-- Just (Matrix [[2,2], [3,5]])
--
-- >>> add (Matrix [[1,2], [3,4]]) (Matrix [])
-- Nothing
add :: Num a => Matrix a -> Matrix a -> Maybe (Matrix a)
add x@(Matrix mx) y@(Matrix my)
  | dimensions x == dimensions y = Just . Matrix $ zipWith (zipWith (+)) mx my
  | otherwise = Nothing

-- | Subtract two matrices if possible, return 'Nothing' otherwise.
-- Matrices are expected to be 'valid'.
--
-- The prime in the function's name avoids a clash with the Prelude's 'subtract'.
--
-- >>> subtract' (Matrix [[1,2], [3,4]]) (Matrix [[1,0], [0,1]])
-- Just (Matrix [[0,2], [3,3]])
--
-- >>> subtract' (Matrix [[1,2], [3,4]]) (Matrix [])
-- Nothing
subtract' :: Num a => Matrix a -> Matrix a -> Maybe (Matrix a)
subtract' x y = add x $ scalarMultiply (-1) y

-- | Multiply two matrices if they can be multipled, returns 'Nothing'
-- otherwise. Matrices are expected to be 'valid'.
--
-- >>> multiply (Matrix [[1,2], [3,4]]) (Matrix [[2,0], [1,1]])
-- Just (Matrix [[4,2], [10,4]])
multiply :: Num a => Matrix a -> Matrix a -> Maybe (Matrix a)
multiply x@(Matrix mx) y@(Matrix my)
  | b == c = Just . Matrix $ map row mx
  | otherwise = Nothing
  where
    (a, b) = dimensions x
    (c, d) = dimensions y
    Matrix ty = transpose y
    row rx = map (sum . zipWith (*) rx) ty

-- | Pretty-print a 'Matrix'. All columns should have same width and should be
-- aligned to the right.
--
-- >>> putStrLn . pprint $ identity 3
-- 1 0 0
-- 0 1 0
-- 0 0 1
--
-- >>>  putStrLn . pprint $ Matrix [[1, 42, 128], [0, 1, 2]]
--   1  42 128
--   0   1   2
pprint :: Show a => Matrix a -> String
pprint (Matrix m) = unlines $ map (unwords . map (pad mx)) sm
  where
    sm = map (map show) m
    mx = maximum $ map (maximum . map length) sm
    pad n x = replicate (n - length x) ' ' ++ x

-- | Compute the determinant of a given 'Matrix'.
-- The input 'Matrix' is expected to be 'valid' and 'square'.
--
-- For simplicity, use the
-- <https://en.wikipedia.org/wiki/Laplace_expansion Laplace expansion> method.
--
-- Implementing this function is optional and awords bonus points for the task.
--
-- >>> determinant (Matrix [[1,5,2], [3,4,0], [0,2,0]])
-- 12
determinant :: Num a => Matrix a -> a
determinant (Matrix []) = 1
--determinant (Matrix [[x]]) = x
--determinant (Matrix [[a,b], [c,d]]) = a*d - b*c
determinant (Matrix (hm:tm)) = sum . setSigns $ zipWith (*) hm (map determinant minors)
  where
    -- adds minus to every second item
    setSigns [] = []
    setSigns [x] = [x]
    setSigns (x:y:xs) = x : -y : setSigns xs
    -- the list of all minors corresponding to the items in the first row
    minors = map Matrix . zipWith (map . dropCol) [0..] $ repeat tm
    -- drop (i+1)-th element of the given list
    dropCol i xs = prefix ++ tail suffix
      where (prefix, suffix) = L.splitAt i xs