Posted By

rtperson on 09/08/11


Tagged

algorithm problems 99 fp


Versions (?)

Haskell 99 Problems, numbers 1 through 9


 / Published in: Haskell
 

URL: http://www.haskell.org/haskellwiki/99_questions/1_to_10

I had originally started these problems from #10 (Run-length encoding). I went back and did 1-8 for completeness.

  1. import Data.List
  2.  
  3. list1 = [1,2,3,4,5,6]
  4.  
  5. -- Problem 1: find the last element of a list
  6. lastList :: [a] -> a
  7. lastList [] = error "list cannot be empty"
  8. lastList (x:[]) = x
  9. lastList (x:xs) = lastList xs
  10.  
  11. -- Problem 2: Find the last but one element of a list.
  12. lastButOne :: [a] -> a
  13. lastButOne [] = error "list cannot be empty"
  14. lastButOne (x:[]) = error "list must be larger than one"
  15. lastButOne [x,_] = x
  16. lastButOne (_:xs) = lastButOne xs
  17.  
  18.  
  19. -- Problem 3: Find the K'th element of a list. The first element in the list is number 1.
  20. elementAt :: [a] -> Int -> a
  21. elementAt [] n = error "list cannot be empty"
  22. elementAt s@(x:xs) n
  23. | n > (length s) = error "n cannot be larger than list"
  24. | otherwise = if (length s) == n then x else elementAt xs n
  25.  
  26. -- Problem 4: find the number of elements of a list
  27. countList :: [a] -> Int
  28. countList [] = 0
  29. countList (x:xs) = 1 + countList xs
  30.  
  31. -- Problem 5: reverse a list (I assume, not using "reverse")
  32. reverse' :: [a] -> [a]
  33. reverse' [] = []
  34. reverse' (x:xs) = reverse' xs ++ (x : [])
  35.  
  36. -- Problem 6: find out whether a list is a palindrome
  37. isPalindrome :: (Eq a) => [a] -> Bool
  38. isPalindrome [] = True
  39. isPalindrome xs = let xs2 = reverse xs
  40. in (xs2 == xs)
  41.  
  42. -- Problem 7: flatten a nested list structure
  43. -- NOTE: This doesn't strictly solve the problem. May want to revisit later.
  44. flatten :: [[a]] -> [a]
  45. flatten = foldr (++) []
  46.  
  47. {-
  48.   Problem 8: Eliminate consecutive duplicates of list elements.
  49.   If a list contains repeated elements they should be replaced with
  50.   a single copy of the element. The order of the elements should not be changed.
  51.  
  52.   > compress ["a","a","a","a","b","c","c","a","a","d","e","e","e","e"]
  53.   ["a","b","c","a","d","e"]
  54.  
  55. -}
  56.  
  57. -- excellent opportunity to play around with mapAccumL
  58. compress :: (Eq x) => [x] -> [x]
  59. compress xs = fst $ mapAccumL (\ys s -> if (length ys > 0) && (last ys == s) then (ys, s) else (ys++s:[], s)) [] xs
  60.  
  61. -- the simplest solution from the Wiki
  62. compress' :: Eq a => [a] -> [a]
  63. compress' = map head . group
  64.  
  65. {-
  66.   Problem 9: Pack consecutive duplicates of list elements into sublists.
  67.   If a list contains repeated elements they should be placed in separate sublists.
  68.  
  69.   *Main> pack ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e']
  70.   ["aaaa","b","cc","aa","d","eeee"]
  71. -}
  72.  
  73. pack :: (Eq a) => [a] -> [[a]]
  74. pack = group

Report this snippet  

You need to login to post a comment.