Haskell. INNER JOIN von zwei Listen

Question

Ich habe Google gefragt und versucht, die dafür erforderlichen Tools zu finden, kann aber anscheinend keine Lösung für mein Problem finden. Die ganze Aufgabe besteht darin, ein Wörterbuch zu verwenden, um eine Liste zu übersetzen und nur die eindeutigen Werte beizubehalten. Zum Beispiel die folgenden Eingaben:

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

sollen folgende Ausgabe liefern:

result = ['aa', 'bb']

Hier stecke ich bisher fest:

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)

was ergibt

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

Also das ich zu lösen dachte, es könnte ein Weg sein , zu verwenden , filteroder mapoder foldlin irgendeiner Weise eine innere zu tun kommen , wie folgt:

let result = innerJoin values result

Derzeit habe ich etwas, das so aussieht:

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)

Aber es kehrt zurück ["aa","bb","c","g"]und nicht das erwartete ["aa","bb"]. Am Ende habe ich vor, es zu beenden nub, aber ich habe Probleme, den innerJoin-Teil herauszufinden.

BEARBEITEN:

Dank der folgenden Antwort ist hier die Lösung für das 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]

Answer 1

Die Funktion, die Sie dafür wünschen, ist lookup. Zum Beispiel:

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

Die andere Funktion, die hier nützlich ist, ist Data.Maybe.catMaybes: Wenn Sie eine Liste mögen [Just 1, Just 2, Nothing, Just 3, Nothing]und catMaybesauf diese anwenden , erhalten Sie [1, 2, 3]. So können Sie einfach kombinieren lookupund catMaybeszu erhalten , catMaybes $ map (flip lookup dict) list1wie Sie die gewünschte Lösung. Eine zusätzliche Verfeinerung besteht darin, zu beachten, dass dies als äquivalent zu Data.Maybedefiniert mapMaybe f xsist catMaybe (map f xs), sodass Sie dies bis auf vereinfachen können mapMaybe (flip lookup dict) list1.