Posts Tagged ‘linked’

Programming Praxis – Three List Exercises

May 7, 2013

In today’s Programming Praxis exercise, we need to implement three functions that work on linked lists. Let’s get started, shall we?

The first function removes every nth element from a list.

deleteNth :: Int -> [a] -> [a]
deleteNth _ [] = []
deleteNth n xs = take (n - 1) xs ++ deleteNth n (drop n xs)

For the second function we need to remove all the duplicate elements of a list. This is the basic O(n^2) version, keep a separate Set or Hashtable for O(n log n) or O(n) performance.

nub :: Eq a => [a] -> [a]
nub = foldl (\a x -> if elem x a then a else a ++ [x]) []

And finally a function to split a list into two halves. This implementation is probably a little slower than the tortess and hare algorithm, but the code is shorter and more self-explanatory.

half :: [a] -> ([a], [a])
half xs = splitAt (div (length xs) 2) xs

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ deleteNth 4 [1..10] == [1,2,3,5,6,7,9,10]
          print $ deleteNth 3 [1,2] == [1,2]
          print $ nub [1..5] == [1..5]
          print $ nub [1,1,2,3,4,5] == [1..5]
          print $ nub [1,1,2,3,4,5] == [1..5]
          print $ nub [1,2,1,3,1,4,1,5,1] == [1..5]
          print $ nub [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5] == [1..5]
          print $ half [1] == ([],[1])
          print $ half [1..5] == ([1,2],[3,4,5])
          print $ half [1..6] == ([1,2,3],[4,5,6])