Haskell 99, Problems 1-10 (simple list processing)

Question

I'm just learning Haskell and I wanted to know if I'm going in the right direction with my solving of the Haskell 99 problems. The file of interest is here which I've also reproduced below.

module OneToTen where
{-- Problem 1: Find the last element of a list. --}
myLast :: [a] -> a
myLast [] = error "Empty list."
myLast [x] = x
myLast (x:xs) = myLast xs
{-- Problem 2: Find the last but one element of a list. --}
myButLast :: [a] -> a
myButLast [] = error "Empty list."
myButLast [x] = error "One element list."
myButLast [x,y] = x
myButLast (x:xs) = myButLast xs
{-- Problem 3: Find the Kth element of a list. The first element in the list
 -- is number 1 --}
elementAt :: [a] -> Int -> a
elementAt [] _ = error "Empty list."
elementAt (x:_) 1 = x
elementAt (_:xs) n = elementAt xs (n-1)
{-- Problem 4: Find the number of elements of a list. --}
myLength :: [a] -> Int
myLength xs = myLengthAux xs 0
myLengthAux :: [a] -> Int -> Int
myLengthAux [] acc = acc
myLengthAux (_:xs) acc = myLengthAux xs (acc+1)
{-- Problem 5: Reverse a list. --}
myReverse :: [a] -> [a]
myReverse xs = myReverseAux xs []
myReverseAux :: [a] -> [a] -> [a]
myReverseAux [] acc = acc
myReverseAux (x:xs) acc = myReverseAux xs (x:acc)
{-- Problem 7: Flatten a nested list structure. --}
data NestedList a = Elem a | List [NestedList a]
flatten :: NestedList a -> [a]
flatten xs = flattenAux xs []
flattenAux :: NestedList a -> [a] -> [a]
flattenAux (List []) acc = acc
flattenAux (Elem x) acc = x:acc
flattenAux (List (x:xs)) acc = flattenAux (List xs) (acc ++ (flattenAux x []))
{-- Problem 8: Eliminate consecutive duplicated of list elements. --}
compress :: (Eq a) => [a] -> [a]
compress [] = []
compress (x:xs) = compressAux xs x [x]
compressAux :: (Eq a) => [a] -> a -> [a] -> [a]
compressAux [] y acc = acc
compressAux (x:xs) y acc | x == y = compressAux xs y acc
 | x /= y = compressAux xs x (acc ++ [x])
{-- 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 [] = error "Empty list."
pack (x:xs) = packAux xs x [x] []
packAux :: (Eq a) => [a] -> a -> [a] -> [[a]] -> [[a]]
packAux [] _ xs acc = acc ++ [xs]
packAux (x:xs) y ys acc | x == y = packAux xs y (y:ys) acc
 | x /= y = packAux xs x [x] (acc ++ [ys])
{-- Problem 10: Run-length encoding of a list. Use the result of problem P09
 -- to implement the so-called run0length encoding data compression method. --}
encode :: (Eq a) => [a] -> [(Int,a)]
encode [] = error "Empty list."
encode xs = map (\ys -> (length ys, head ys)) (pack xs)

I'm most curious if implementing all of these auxiliary methods is standard practice? It's easier for me to think of a recursive problem using an accumulator, consequently, I write most of them this way. Is this correct? Should I be writing them differently?

• GeneralBecos: myLast is the same as tail. and myButLast is last.tail.

Answer 1

Solutions 1 and 2 are fine.

Solution 3: Find the Kth element of a list

The error message for 3 is a bit misleading: you can also get the error if the requested index is beyond the end of the list. Strictly speaking, it should be an error to request a non-positive index as well.

Solution 4: Find the number of elements of a list

You should not need a helper function.

myLength :: [a] -> Int
myLength [] = 0
myLength (x:xs) = 1 + myLength xs

However, as @Franky points out, using a helper function can make it tail-recursive.

Solution 5: Reverse a list

You could write it as myReverse (x:xs) = (myReverse xs) ++ x, but it is much more efficient the way you wrote it using a helper function. The helper should be scoped using a where clause (or let ... in, which does the same thing). It is customary to name trivial helper functions using the myReverse' convention.

myReverse :: [a] -> [a]
myReverse xs = myReverse' xs []
 where
 myReverse' [] rev = rev
 myReverse' (x:xs) rev = myReverse' xs (x:rev)

Solution 7: Flatten a nested list structure.

No helper is necessary.

data NestedList a = Elem a | List [NestedList a]
flatten :: NestedList a -> [a]
flatten (Elem x) = [x]
flatten (List []) = []
flatten (List (x:xs)) = flatten x ++ flatten (List xs)

Solution 8: Eliminate consecutive duplicated list elements

Again, no helper or accumulator is necessary. Furthermore, you should avoid ++, as it works by inefficiently walking to the end of its LHS argument.

compress :: Eq a => [a] -> [a]
compress [] = []
compress (x:[]) = [x]
compress (x:y:zs)
 | x == y = compress (y:zs)
 | otherwise = x : compress (y:zs)

Problem 9: Pack consecutive duplicates of list elements into sublists

I don't think that packing an empty list should be an error. Rather it should just return an empty list.

My advice is similar to the above. I think that a helper function is needed, but not in that way.

pack :: Eq a => [a] -> [[a]]
pack [] = []
pack (x:xs) = pack' [x] xs
 where
 pack' run [] = [run]
 pack' run@(r:_) (x:xs)
 | x == r = pack' (x:run) xs
 | otherwise = run : pack' [x] xs

Problem 10: Run-length encoding of a list

Again, I don't think that encoding an empty list should be an error.

The implementation would read more nicely, in my opinion, using a list comprehension and better naming.

encode :: Eq a => [a] -> [(Int, a)]
encode xs = [(length run, head run) | run <- pack xs]

---

In summary, accumulators are sometimes the right approach (as in myReverse), but often they are harmful. Before using one, think hard about whether it is necessary and efficient.

• Franky: Solution 4: The @emmruld helper function is tail recursive, yours not. Not that it matters unless strictness is added.