Why do I get this error about empty list?

user_11346784 0
Viewed 536

I have made these functions:

-- Looks up in dict and returns Maybe key
myLookUp :: [(String, [String])] -> String -> String
myLookUp [] val = []
myLookUp ((k, vs):ds) val
  | val `elem` snd (myLast ds) = myCensor val
  | val `elem` vs = k
  | otherwise = myLookUp ds val

-- Given a dict of tuples of strings and list of strings, 
-- should return the last tuple in dict
myLast :: [(String, [String])] -> (String, [String])
myLast [] = error "Empty list"
myLast [x] = x
myLast (x:xs) = myLast xs

Which compiles, but when I try to test it I get an error saying

ghci> myLookUp [("strength", ["ignorance"]), ("bla", ["blabla", "blabla"])] "aa"

*** Exception: Empty list
CallStack (from HasCallStack):
  error, called at test.hs:103:13 in main:Main

And if I try to remove my base case myLast [] = error "Empty list" I get this error:

 myLookUp [("strength", ["ignorance"]), ("bla", ["blabla", "blabla"])] "aa"

    *** Exception: test.hs:(104,1)-(105,25): 
    Non-exhaustive patterns in function myLast

I think that myLast works because I get this output:

myLast [("strength", ["ignorance"]), ("bla", ["blabla", "blabla"])]
("bla",["blabla","blabla"])

And I thought I could use snd on the tuple to get the list-element, but since I get this error, I'm uncertain as to what I am doing wrong.

recursion haskell
2 Answers

Try to think a little closer about what you are trying to do. The reason you get an empty list exception here is because you try to pass myLast a list that may be empty (and will be empty by the last iteration). You have no check in your guards for when there is a single element left in the input list (ds). You can do this by adding:

| null ds = []

Or check for a single element in the function pattern. Furthermore the myLast function is identical to the built in prelude function "last", so it could replace that. Also keep in mind where you place your null check for ds, it has to be before you attempt to use ds, but after your first check:

myLookUp :: [(String, [String])] -> String -> String
myLookUp [] val = []
myLookUp ((k, vs):ds) val
  | val `elem` vs = k
  | null ds = []
  | val `elem` snd (last ds) = myCensor val
  | otherwise = myLookUp ds val

A better approach to this problem is to only check against the elements that are in the head per iteration, it is wildly inefficient to check the last element on every single iteration, when you only have to do it once, and it will be done on the last iteration of the recursive loop anyways.

user_154319970

Here's what it seems like you're trying to do:

Given a dictionary mapping keys (strings) to values (lists of strings), and a string-value to look up, first determine if the given value is present in the list contained in the last entry of the dictionary. If so, then censor the value and return it. Otherwise, determine if the given value is present in some value-list; if so, return the associated key. If not, return Nothing.

Wouldn't it make more sense to have the "list of strings that need censorship" be a separate argument? Then a solution would be:

import Data.List (find)

myLookup :: [String] -> [(String, [String])] -> String -> Maybe String
myLookup toCensor dict val
  | val `elem` toCensor = Just $ myCensor val
  | Just (key, _) <- find (\(_, vs) -> val `elem` vs) dict = Just key
  | otherwise = Nothing
user_153265440
Related