How do I iterate through two lists simultaneously in Haskell?-CodePudding

Essentially what I want to do is this: Given a list comprised of tuples [(x,[y])] and another list of strings [a], I want to create a new list of all the [y]'s where x == a if that makes sense, so if I have [('a', ['z', 'k', 'x']), ('b', ['z']), ('c', ['y', 'j'])] and ['a', 'c'], the resulting list when both lists are passed through the function would be [['z', 'k', 'x'], ['y', 'j']].

The solution I came up with is kind of ridiculous and over complicated, (as well as non-functional) but just so you can see what kind of path I've been thinking about I'll post it below.

foo ys xs acc = map (\x -> (map (\(a,y) -> if x == a then y:acc else []) ys)) xs

This prints what I want but also prints tons of extra brackets that makes the output super confusing, no doubt because I've bastardized the map function. Any suggestions?

CodePudding user response：

Given

l1 = [('a', ['z', 'k', 'x']), ('b', ['z']), ('c', ['y', 'j'])]
l2 = ['a', 'c']

a quick and intuitive solution is

filter (\(c,_) -> c `elem` l2) l1

which filters l1 retaining only those pairs whose first element is an element of l2.

The filtering predicate (\(c,_) -> c `elem` l2) can also be written as ((`elem` l2) . fst).

As regards performance, if the fact that l2 is sorted and l1 is sorted with respect to the fsts is just a matter of concidence or oversimplification of the example, we can observe that filtering is a linear operation, because you have to traverse all the elements of l1 to decide if each one has to be retained or filtered out. But maybe the look up operated by `elem` l2 can be improved by making l2 a Set, which is done by simply changing `elem` l2 to `elem` Data.Set.fromList l2.

If, instead, the lists are truly sorted as in the example, then other approaches are possible. Just as an example, if l1 was the same as above, but l2 was ['d', {-whatever-}], then you'd know that the output is empty.

CodePudding user response：

Assuming the two lists are sorted, like in your example, then you can iterate through both lists simultaneously, using pattern-matching and guards:

foo ((x,y):xs) (z:zs) | x == z =
foo ((x,_):xs) (z:zs) | x < z =
foo ((x,y):xs) (z:zs) | x > z =
foo [] _ =
foo _ [] =

I have intentionally blanked everything after the = sign, because I believe you'll learn more if you fill it yourself than if I dump a solution. Although I did leave a small hint by including y where it's needed, and _ instead where it's not needed.

Testing:

ghci> foo [('a', ['z', 'k', 'x']), ('b', ['z']), ('c', ['y', 'j'])] ['a', 'c']
["zkx","yj"]