module Sol01 where

import HL01GS

-- | 1.9 Define a function that gives the maximum of a list of integers. Use the predefined function max.
-- >>> mxmInt [1, 44, 56, 2, 3]
-- 56
mxmInt :: [Int] -> Int
mxmInt [] = error "empty list"
mxmInt [x] = x
mxmInt (x : xs) = max x (mxmInt xs)

-- | 1.10 Define a function removeFst that removes the first occurrence of an integer m from a list of integers. If m does not occur in the list, the list remains unchanged.
-- >>> removeFst 5 [1, 5, 6, 5]
-- [1,6,5]
removeFst :: (Eq a) => a -> [a] -> [a]
removeFst x [] = []
removeFst x (y : ys)
  | x == y = ys
  | otherwise = y : (removeFst x ys)

-- | 1.13 Write a function count for counting the number of occurrences of a character in a string. In Haskell, a character is an object of type Char, and a string an object of type String, so the type declaration should run: count :: Char -> String -> Int.
-- >>> count 'e' "Discrete Math, eek"
-- 4
count :: Char -> String -> Int
count c [] = 0
count c (x : xs)
  | c == x = 1 + (count c xs)
  | otherwise = (count c xs)

-- 1.14 A function for transforming strings into strings is of type String -> String. Write a function blowup that converts a string a1 a2 a3 · · · to a1 a2 a2 a3 a3 a3 · · · . blowup "bang!" should yield "baannngggg!!!!!". (Hint: use ++ for string concatenation.)

-- | A helper for a helper.
-- >>> copy 5 'a'
-- "aaaaa"
copy :: Int -> Char -> String
copy 0 c = []
copy n c = c : (copy (n - 1) c)

-- | A helper for blowup, which includes start count.
-- >>> blowup' "hi" 5
-- "hhhhhiiiiii"
blowup' :: String -> Int -> String
blowup' [] n = []
blowup' (x : xs) n = (copy n x) ++ (blowup' xs (n + 1))

-- | The actual blowup function, which starts at 1.
-- >>> blowup "Discrete"
-- "Diisssccccrrrrreeeeeettttttteeeeeeee"
blowup :: String -> String
blowup xs = blowup' xs 1

-- Haskell hackers may appreciate the following alternative.
-- To understand the details, look up the code for zip, take and repeat in Prelude.

-- | Like blowup, spread the word!
-- >>> spread "Math"
-- "Maattthhhh"
spread :: [a] -> [a]
spread xs = [x | (n, y) <- zip [1 ..] xs, x <- take n (repeat y)]

-- 1.15 Write a function srtString :: [String] -> [String] that sorts a list of strings in alphabetical order.
-- The best way to approach this is to generalize mnmInt and srtInt,
-- and use these to implement a general sorting algorithm based on insertion.
-- In Haskell, types for which we can do size comparison,
-- are put in a so-called type class, the type class Ord.
-- In Haskell, we can make this type class requirement part of the type declaration.
-- f :: Ord a => a means that f is a type in class Ord.
-- f :: Ord a => [a] -> a means that f is a function from lists over a to a objects,
-- where a is a type in class Ord.
-- In other words, f picks an object from a list of things,
-- where the list contains objects that can be compared for size.
-- That is the type we need for the generalized minimum function.

-- | A helper function. String ord, like string sort. Think dictonary sorting.
-- >>> mnm ["bad", "good"]
-- "bad"
mnm :: (Ord a) => [a] -> a
mnm [] = error "empty list"
mnm [x] = x
mnm (x : xs) = min x (mnm xs)

-- | a sorting function:
-- >>> srt ["good", "bad", "awesome", "terrible"]
-- ["awesome","bad","good","terrible"]
srt :: (Ord a) => [a] -> [a]
srt [] = []
srt xs = m : (srt (removeFst m xs)) where m = mnm xs

-- 1.17 Write a function: substring :: String -> String -> Bool
-- that checks whether str1 is a substring of str2.
-- The substrings of an arbitrary string ys are given by:
-- 1. if xs is a prefix of ys, xs is a substring of ys,
-- 2. if ys equals y:ys’ and xs is a substring of ys’, xs is a substring of ys,
-- 3. nothing else is a substring of ys.

-- | Detects if first string is a subset of the second string. This should help you be less confused...
-- >>> substring "bob" "combobulate"
-- True
substring :: String -> String -> Bool
substring [] ys = True
substring (x : xs) [] = False
substring (x : xs) (y : ys) =
  ((x == y) && (prefix xs ys))
    || (substring (x : xs) ys)

-- | 1.20 Use map to write a function lengths that takes a list of lists and returns a list of the corresponding list lengths.
-- >>> lengths [[1,2,3],[1,2,3,4]]
-- [3,4]

-- | Strings are lists of Char in Haskell. The function is polymorphic.
-- >>> lengths ["Discrete", "Math"]
-- [8,4]
lengths :: [[a]] -> [Int]
lengths = map length

-- | 1.21 Use map to write a function sumLengths, that takes a list of lists and returns the sum of their lengths.
-- >>> sumLengths [[1,2,3],[1,2,3,4]]
-- 7
sumLengths :: [[a]] -> Int
sumLengths lists = sum (map length lists)

-- | Here is another way to express this, using (.) for function composition:
-- >>> sumLengths' ["Discrete", "Math"]
-- 12
sumLengths' :: [[a]] -> Int
sumLengths' = sum . lengths