Haskell. INNER JOIN dari dua daftar

Question

Saya telah bertanya kepada google dan mencoba menemukan alat yang diperlukan untuk melakukan ini, tetapi tampaknya tidak dapat menemukan solusi untuk masalah saya. Keseluruhan tugas adalah menggunakan kamus untuk menerjemahkan daftar dan hanya menyimpan nilai uniknya. Misalnya masukan berikut:

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

seharusnya menghasilkan keluaran berikut:

result = ['aa', 'bb']

Di sinilah saya terjebak sejauh ini:

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)

yang menghasilkan

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

Jadi untuk mengatasi ini, saya berpikir bahwa mungkin ada cara untuk menggunakan filteratau mapatau melakukan foldlbeberapa cara untuk melakukan inner join sebagai berikut:

let result = innerJoin values result

Saat ini saya memiliki sesuatu yang terlihat seperti ini:

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)

Tapi itu kembali ["aa","bb","c","g"]dan bukan yang diharapkan ["aa","bb"]. Pada akhirnya saya berencana untuk menyelesaikannya nub, tetapi saya berjuang dengan mencari tahu bagian innerJoin.

EDIT:

Berkat jawaban di bawah ini adalah solusi untuk masalah tersebut:

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

Fungsi yang Anda inginkan untuk ini adalah lookup. Misalnya:

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

Fungsi lain yang berguna di sini adalah Data.Maybe.catMaybes: jika Anda memiliki daftar seperti [Just 1, Just 2, Nothing, Just 3, Nothing]dan menerapkannya catMaybes, Anda mendapatkan [1, 2, 3]. Jadi Anda bisa menggabungkan lookupdan catMaybesmendapatkan catMaybes $ map (flip lookup dict) list1solusi yang Anda inginkan. Perbaikan tambahan adalah untuk dicatat yang Data.Maybemendefinisikan mapMaybe f xssebagai yang setara catMaybe (map f xs), sehingga Anda dapat menyederhanakannya menjadi mapMaybe (flip lookup dict) list1.