--Sample Sequences
icecream = "icecream"
scheme = "scheme"
saturn = "saturn"  -- "saaturn"
mad = ['m','a','d']
hatter = ['h','a','t','t','e','r']
hate = ['h','a','t','e']
snowball = ['s','n','o','w','b','a','l','l']
computer = ['c','o','m','p','u','t','e','r']
coffee = ['c','o','f','f','e','e']


--Function that's called in a console window which does the sequence 
--alignment and puts the two optimal sequences back together
printSeq :: String -> String -> (String,String)
printSeq s1 s2 = unzip (getSeq s1 s2)


--Main function of the program which does the actual sequence alignment
getSeq :: String -> String -> [(Char,Char)]
getSeq [] [] = []
getSeq [] s2 = case2 [] s2
getSeq s1 [] = case3 s1 []
getSeq s1 s2 = let a1 = case1 s1 s2;
                   a2 = case2 s1 s2;
                   a3 = case3 s1 s2;
               in maxSeq a1 a2 a3


case1 :: [Char] -> [Char] -> [(Char,Char)]
case1 s1 s2 = [(head s1,head s2)] ++ getSeq (tail s1) (tail s2)

case2 :: [Char] -> [Char] -> [(Char,Char)]
case2 s1 s2 = [('-',head s2)] ++ getSeq s1 (tail s2)

case3 :: [Char] -> [Char] -> [(Char,Char)]
case3 s1 s2 = [(head s1,'-')] ++ getSeq (tail s1) s2


--Grab the score of one tuple (a possible alignment)
score :: (Eq a) => (a,a) -> Integer
score (c1,c2) | c1==c2    = 1
              | otherwise = -1
            
--Sum up the score for a sequence
scoreSum :: (Eq a) => [(a,a)] -> Integer
scoreSum seq = sum $ map score seq


--Returns a solution
maxSeq :: (Eq a) => [(a,a)] -> [(a,a)] -> [(a,a)] -> [(a,a)]
maxSeq a1 a2 a3
      | s1 == s2 && s1 == s3 = [a1,a2,a3]
	| s1 == s2 && s1 > s3 =  [a1,a2]
	| s1 == s3 && s1 > s2 =  [a1,a3]
	| s2 == s3 && s2 > s1 =  [a2,a3]
	| s1 > s2 && s1 > s3 =   [a1]
      | s2 > s1 && s2 > s3 =   [a2]
      | otherwise          =   [a3]
        where s1 = scoreSum a1
              s2 = scoreSum a2
              s3 = scoreSum a3