99 problems in Haskell, 11-20

-- Problem 11: Modified run-length encoding.
-- A data type showing "frequency", if you will:
data ListItem a = Single a | Multiple Int a
    deriving (Show)

encode_modified :: (Eq a) => [a] -> [ListItem a]
-- The solution is just like problem 10, actually, in a list comprehension:
encode_modified xs = [y | x <- group xs, let y = if (length x) == 1 then Single (head x) else Multiple (length x) (head x)]

-- Problem 12: Decode a run-length encoded list. The inverse of problem 11:
decode_modified = concatMap f
                  where f (Single x) = [x]
                        f (Multiple n x) = (replicate n x)


-- Problem 13: Run-length encoding of a list with counting. We already did this for
-- problem 9, so the solution is equally straightforward. First we split the list into
-- duplicates and not, then we count duplicates, then use guards to distinguish
-- the no-duplicates case:
encode_direct :: (Eq a) => [a] -> [ListItem a]
encode_direct [] = []
encode_direct (x:xs) | count == 1 = (Single x) : (encode_direct xs)
                     | otherwise  = (Multiple count x) : (encode_direct rest)
                     where (dupes, rest) = span (==x) xs
                           count = 1 + (length dupes)

-- Problem 14: Duplicate the elements of a list. There are many ways to solve this, but I
-- went for the Prelude one:
dupli :: [a] -> [a]
dupli = concatMap (replicate 2)

-- Problem 15: Replicate the elements of a list a given number of times.
-- The solution is in the problem statement, really ^_^ :
repli :: Foldable t => t b -> Int -> [b]
repli xs n = concatMap (replicate n) xs

-- Problem 16: Drop every Nth element from a list:
-- This is an exercise in naming, in my opinion. The fact that some Haskell functions are
-- named in a certain way (`drop`), helps you reason about this problem statement.
-- Likewise, if you name your functions in a short, concise manner, they will help you
-- build bigger programs and be more useful in the future.
-- How do you drop the Nth element from a list? You take the first N-1, drop one, repeat
-- on the rest of the list, iteratively or recursively:
drop_every :: [a] -> Int -> [a]
drop_every [] _ = []
drop_every xs n = (take (n-1) xs) ++ drop_every (drop n xs) n

-- Problem 17: Split a list into two parts, the length of the first part is given.
-- This is when it first occurred to me that solutions of this form are what `foldl` is
-- actually about, but writing this particular one using `foldl` makes it overly verbose:
split :: [a] -> Int -> ([a], [a])
split [] _ = ([], [])
split l@(x : xs) n | n > 0 = (x : ys, zs)
                   | otherwise = ([], l)
                where (ys, zs) = split xs (n - 1)

-- Problem 18: Extract a slice from a list.
-- This one doesn't prohibit us from using predefined predicates, so use Prelude:
slice :: [a] -> Int -> Int -> [a]
slice xs n m | n > 0 = take (m - n + 1) $ drop (n - 1) xs

-- Problem 19: Rotate a list N places to the left.
-- As you might know, rotating a list (xs) amounts to taking a slice from (xs:xs). That's
-- applicable to all rotations BTW, like rotating bit sequences, etc.
-- Instead of producing (xs:xs), I used `cycle`:
rotate :: [a] -> Int -> [a]
rotate xs n = take (length xs) $ drop (length xs + n) $ cycle xs

-- Problem 20: Remove the Kth element from a list.
-- Why K and not N? :P
-- `take` and `drop` are just too useful:
remove_at xs n | n > 0 = take (n - 1) xs ++ drop n xs
               | otherwise = xs