CODEWITHSUNDEEP
haskell
mushishi
mushishi

Reputation: 151

Haskell function on list of tuples

Task (home assignment) : Given a list of integers, return a list of tuples where each tuple in the list has the form (int_val, val_freq). No built-in functions are allowed. Allowed operators: :, ++.

Attempt 1: 

simplify :: [ Int ] -> [( Int , Int )]
simplify [] = []
simplify ((x:xs) ++ [(a, b)]) = 
  if x == a then (simplify xs ++ [(x, b + 1)])
  else  (simplify xs ++ [(x, 0)])

Attempt 2: 

naive_enumerate :: [ Int ] -> [( Int , Int )]
naive_enumerate [] = []
naive_enumerate x:xs = 
  if x == y then [(y, 1)] ++ naive_enumerate xs

enumerate_tuple_list :: [( Int , Int )] -> [( Int , Int )]
enumerate_tuple_list [] = []
enumerate_tuple_list ((a, b):(c, d):rest) = 
  if (a == c) then (a, b+d):(enumerate_tuple_list rest)
  else (a, b+d):(enumerate_tuple_list rest)


simplify :: [ Int ] -> [( Int , Int )]
simplify some_list = enumerate_tuple_list (naive_enumerate some_list)

Expected: For e.g. input of [1, 2, 2, 3] an output of [(1,1), (2, 2), (3,1)]. Actual result: in attempt 1, I got an error at

simplify ((x:xs) ++ [(a, b)]) =

In attempt 2, my parse error occurs at

enumerate_tuple_list :: [( Int , Int )] -> [( Int , Int )]

Questions:

  1. What is the correct syntax to iterate over tuples in a list?

  2. Can you explain why I get both parser errors?

  3. Why does Haskell forbid code like the following:

    naive_enumerate x:xs = [(x, 1)] ++ naive_enumerate xs

Update: Attempt 3: Thanks to the suggestions so far, I now have

simplify :: [ Int ] -> [( Int , Int )]
simplify [] = []
simplify (x:xs) = let recursive_result = simplify xs
                  update n ((a, b):pairs) = 
                      if n == a then ((a, b + 1):pairs)
                      else ((n, 1):pairs)
                  in update x recursive_result

Now the code compiles, but I get the following error:

Exception: ... Non-exhaustive patterns in function update

Hence the additional questions:

  1. Which case(s) am I missing?

  2. Is it possible to catch the error at compile time (debug/verbose options don't do the trick)?

Upvotes: 0

Views: 2498

Answers (2)

mushishi
mushishi

Reputation: 151

First of all, thanks to all respondents. I will answer all my questions here and at the end of the answer provide a (spoiler) sample solution.

  1. What is the correct syntax to iterate over tuples in a list?

Lists should not be iterated over. To write a function on such a data structure,

function_name ((element1, element2, ..., elementN):some_list) = result

My error was that I disregarded the binding priority of the list creation constructor : and function application.

  1. Can you explain why I get both parser errors?

Answered already.

  1. Why does Haskell forbid code like the following:

Explained by chepner.

  1. Which case(s) am I missing?

The case that there are 1-element-lists.

  1. Is it possible to catch the error at compile time?

Possible by using HTF.

SPOILER ALERT And here comes my Attempt 5:

simplify :: [ Int ] -> [( Int , Int )]
simplify [] = []
simplify (x:xs) = let recursive_result = simplify xs
                  update n [] = [(n, 1)]
                  update n ((a, b):pairs) = 
                      if n == a then ((a, b + 1):pairs)
                      else (a, b):(update n pairs)
              in update x recursive_result

Upvotes: 0

chepner
chepner

Reputation: 532428

You are currently trying to iterate over your return value as if it were an argument. You need to make the recursive call first, then update that result

simplify [] = []
simplify (x:xs) = let recursive_result = simplify xs
                      update n pairs = ...
                  in update x recursive_result

where ... is where you try to find and replace the pair which already contains x, or add a new pair.

Hint: the builtin lookup function would help, if you can convince your teacher to let you use it.

Upvotes: 1

Related Questions