CODEWITHSUNDEEP
haskell
mkalns
mkalns

Reputation: 15

Haskell. INNER JOIN of two lists

I have been asking google and trying to find the necessary tools to do this, but can't seem to find a solution to my problem. The whole task is to use a dictionary to translate a list and keep only the unique values. For example the following inputs:

dict = [("a", "aa"), ("b", "bb")]
list1 = ["a","b","c","a","a","g"]

are supposed to yield the following output:

result = ['aa', 'bb']

This is here where I am stuck at so far:

main = do
    let dict = [("a", "aa"), ("b", "bb")]
    let list1 = ["a","b","c","g"]
    let keys = map fst dict
    let values = map snd dict
    let result = replace keys values list1
    print(result)

which yields

["aa","bb","c","g"]

So to solve this I was thinking that there might be a way to use filter or map or foldl in some way to do an inner join as follows:

let result = innerJoin values result

Currently I have something that looks like this:

innerJoin :: (Eq a) =>[a] -> [a] -> [a]
innerJoin xs     []     = xs
innerJoin []     ys     = ys
innerJoin (x:xs) (y:ys) = if (elem x (y:ys))
                         then x: innerJoin xs ys
                         else innerJoin xs ys


main = do
    let dict = [("a", "aa"), ("b", "bb")]
    let list1 = ["a","b","c","g"]
    let keys = map fst dict
    let values = map snd dict
    let list2 = innerJoin keys list1
    let result = replace keys values list2
    print(result)

But it returns ["aa","bb","c","g"] and not the expected ["aa","bb"]. In the end I plan to finish it off with nub, but I am struggling with figuring out the innerJoin part.

EDIT:

Thanks to the answer below here is the solution to the problem:

innerJoin xs     []     = []
innerJoin []     ys     = []
innerJoin (x:xs) (y:ys) = if (elem x (y:ys))
                         then x: innerJoin xs ys
                         else innerJoin xs ys
catMaybes ls = [x | Just x <- ls]
genList x [] = []
genList [] y = []
genList x (y:ys) = lookup y x: genList x ys
func dict list =  do
    let keys = map fst dict
    let list1 = innerJoin keys list
    catMaybes (genList dict list1)
test1 = func [("a", "aa"),("e", "bb")] ["a","b","c","g","a"]
test2 = func [(1,11),(2,11),(4,44)] [1,2,3,1,2]

Upvotes: 0

Views: 211

Answers (1)

bradrn
bradrn

Reputation: 8467

The function you want for this is lookup. For instance:

lookup "a" [("a", "aa"), ("b", "bb")] = Just "aa"
lookup "b" [("a", "aa"), ("b", "bb")] = Just "bb"
lookup "x" [("a", "aa"), ("b", "bb")] = Nothing   -- "x" is not in the list

The other function which is useful here is Data.Maybe.catMaybes: if you have a list like [Just 1, Just 2, Nothing, Just 3, Nothing] and apply catMaybes to it, you get [1, 2, 3]. So you can just combine lookup and catMaybes to get catMaybes $ map (flip lookup dict) list1 as your desired solution. An additional refinement is to note that Data.Maybe defines mapMaybe f xs as being equivalent to catMaybe (map f xs), so you can simplify that down to mapMaybe (flip lookup dict) list1.

Upvotes: 3

Related Questions