99 problems in Haskell, 1-10

2015 Jul 24

To celebrate trying to learn Haskell for a few weeks now, I figured I’d do a quick rundown of 99 Haskell Problems, as I try to solve them1.

I’ll try and post my ‘solutions’ as soon as it satisfies the problem definition; in that sense, I expect they’ll appear very crude to Haskell veterans but hey, when was that ever a showstopper? Here we go with problems 1-10:

-- Problem 1: Find the last element of a list.
-- First thought that came to mind was to recursively exhaust the list (from Erlang
-- tutorial time):
mylast :: [a] -> a
mylast [] = error "empty list"
mylast [x] = x
mylast (_:xs) = mylast xs

-- Problem 2: Find the last but one element of a list:
lastbutone :: [a] -> a
lastbutone [] = error "empty list"
lastbutone [x] = error "single element list"
lastbutone [x, _] = x
lastbutone (_:xs) = lastbutone xs

-- Problem 3: Find the k'th element of a list. The first element in the list is number 1.
-- It was somewhat surprising for me that counting wasn't exactly necessary for it:
elementAt :: [a] -> Int -> a
elementAt xs n = last (take n xs)

-- Problem 4: Find the number of elements of a list. Recursive counting!
mylength :: [a] -> Int
mylength [] = 0
mylength (_:xs) = 1 + mylength xs

-- Problem 5: Reverse a list. Soon to appear in your job interviews:
myreverse :: [a] -> [a]
myreverse [] = []
myreverse xs = myreverse (tail xs) ++ [head xs]

-- Problem 6: Find out whether a list is a palindrome.
-- Palindromes are easy, so here's the first interesting view at [type constraints](https://en.wikibooks.org/wiki/Haskell/Classes_and_types#Type_constraints).
-- `(Eq a)` constraints `a` to instances of type `Eq`, informally meaning that the
-- argument to isPalindrome is a list of things which support equality and inequality:
isPalindrome :: (Eq a) => [a] -> Bool
isPalindrome [] = True
isPalindrome [_] = True
isPalindrome xs = (head xs) == (last xs) && (isPalindrome (init (tail xs)))

-- Problem 7: Flatten a nested list structure:
-- This is my first contact with type definitions. A nested list is quite simple to define
-- recursively:
data NestedList a = Elem a | List [NestedList a]

myflatten :: NestedList a -> [a]
myflatten (Elem x) = [x]
myflatten (List []) = []
-- Then I will process it recursively as well:
myflatten (List (x:xs)) = myflatten x ++ myflatten (List xs)

-- Problem 8: Eliminate consecutive duplicates of list elements:
compress :: (Eq a) => [a] -> [a]
-- The argument here might be a bit frightening at first. What I want is to refer to the
-- first element of a list, and the "first of the rest". If the first (x) is equal to the
-- first of the rest (y), then I can ignore it (x) - or consume it, if you will - and move
-- onward to the rest of the list. The pattern match xs@(y:_) gives us that capability.
-- Think of it as preserving only the last of consecutive duplicates in the list:
compress (x:xs@(y:_))
        | x == y    = compress xs
        | otherwise = x : compress xs
compress xs = xs

-- Problem 9: Pack consecutive duplicates of list elements into sublists. If a list
-- contains repeated elements they should be placed in separate sublists:
pack :: (Eq a) => [a] -> [[a]]
pack [] = []
-- We split elements of a list recursively into those which are equal to the first one,
-- and those that are not. Then do the same for the latter:
pack (x:xs) = let (first, rest) = span (==x) xs
              in (x:first) : pack rest

-- Problem 10: Run-length encoding of a list:
-- This is incidentally, super-easy. Haskell has the `group` function, which is
-- essentially `pack` from problem 9. All we need to do here is count the length of the
-- sublists, and prepend it to a pair:
encode :: (Eq a) => [a] -> [(Int, a)]
encode xs = map (\x -> (length x, head x)) (group xs)
  1. ± a month 

« Past Future »