Haskell. INNER JOIN de deux listes

Question

J'ai demandé à Google et essayé de trouver les outils nécessaires pour ce faire, mais je n'arrive pas à trouver une solution à mon problème. Toute la tâche consiste à utiliser un dictionnaire pour traduire une liste et ne conserver que les valeurs uniques. Par exemple les entrées suivantes:

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

sont censés produire la sortie suivante:

result = ['aa', 'bb']

C'est ici où je suis coincé jusqu'à présent:

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)

qui donne

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

Donc, pour résoudre ce problème, je pensais qu'il pourrait y avoir un moyen d'utiliser filterou mapou foldld'une manière quelconque de faire une jointure interne comme suit:

let result = innerJoin values result

Actuellement, j'ai quelque chose qui ressemble à ceci:

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)

Mais ça revient ["aa","bb","c","g"]et pas l'attendu ["aa","bb"]. En fin de compte, j'ai l'intention de le terminer avec nub, mais j'ai du mal à comprendre la partie innerJoin.

ÉDITER:

Grâce à la réponse ci-dessous, voici la solution au problème:

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]

Answer 1

La fonction que vous souhaitez pour cela est lookup. Par exemple:

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

L'autre fonction qui est utile ici est la suivante Data.Maybe.catMaybes: si vous avez une liste similaire [Just 1, Just 2, Nothing, Just 3, Nothing]et que vous y appliquez catMaybes, vous obtenez [1, 2, 3]. Ainsi, vous pouvez simplement combiner lookupet catMaybesobtenir catMaybes $ map (flip lookup dict) list1la solution souhaitée. Un raffinement supplémentaire est de noter que Data.Maybedéfinit mapMaybe f xscomme étant équivalent à catMaybe (map f xs), vous pouvez donc simplifier cela jusqu'à mapMaybe (flip lookup dict) list1.