How to check if all Strings in a list are present in a String list of tuples

user_17135388 0
Viewed 66

I am still trying to better understand lists and tuples within Haskell, and I have come across a problem that I cannot seem to get.

I have a func with type:

func :: [String] -> [(String,String)] -> Bool

where i am trying to see if every value in the string list is present within our list of string tuples

For example input and output, let's say I call func ["Thomas","Jeff"] [("Thomas", "22"), ("Jeff", "16")] this should return true

Whereas if I try func ["Brian","Jeff"] [("Thomas", "22"), ("Jeff", "16")] this should return false

This is what I have so far:

func:: [String] -> [(String,String)] -> Bool 
func [] ((y,z):ys)     = True
func (x:xs) []         = False
func (x:xs) ((y,z):ys) 
  | x == y || x == z = func xs ((y,z):ys)
  | otherwise        = func (x:xs) ys

Can anyone see where I am going wrong?

haskell
1 Answers

First, we should collapse that [(String, String)] into a [String], since we're not making use of its pair structure:

flatten :: [(a, a)] -> [a]
flatten = foldr (\(x, y) tl -> x : y : tl) []

(Note that flatten = map fst is insufficient, since x == y || x == z in the questioner's program implies that either the first or second element can be matched against.)

Next, for each string in the first list, we check whether it is present in the second list:

allPresent :: Eq a => [a] -> [a] -> Bool
allPresent xs ys = all (`elem` ys) xs

Then func is simply the composition of these:

func :: Eq a => [a] -> [(a, a)] -> Bool
func xs ys = allPresent xs (flatten ys)

What's wrong with your implementation? First, your first two clauses are overly specific. func [] ys is True regardless of ys, so there's no need to specify that ys is non-empty. Second, the third clause drops the first pair when recursing, so something like func ["Jeff", "Thomas"] [("Thomas", "22"), ("Jeff", "16")] would be erroneously false. A correct implementation in this style would be

func :: forall a. Eq a => [a] -> [(a, a)] -> Bool
func [] _ = True
func (x:xs) ys = go x ys && func xs ys
  where
    go :: a -> [(a, a)] -> Bool
    go _ [] = False
    go x ((y1, y2):ys)
      | x == y1 || x == y2 = True
      | otherwise = go x ys
user_153265440
Related