Haskell INNER JOIN จากสองรายการ

Question

ฉันถาม Google และพยายามหาเครื่องมือที่จำเป็นในการทำสิ่งนี้ แต่ดูเหมือนจะหาวิธีแก้ปัญหาไม่ได้ งานทั้งหมดคือการใช้พจนานุกรมเพื่อแปลรายการและเก็บเฉพาะค่าที่ไม่ซ้ำกัน ตัวอย่างเช่นอินพุตต่อไปนี้:

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

ควรจะให้ผลลัพธ์ต่อไปนี้:

result = ['aa', 'bb']

นี่คือจุดที่ฉันติดอยู่ที่นี่:

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)

ซึ่งให้ผลตอบแทน

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

ดังนั้นเพื่อแก้ปัญหานี้ฉันคิดว่าอาจมีวิธีใช้filterหรือmapหรือfoldlด้วยวิธีใดวิธีหนึ่งในการทำการรวมภายในดังนี้:

let result = innerJoin values result

ตอนนี้ฉันมีบางอย่างที่มีลักษณะดังนี้:

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)

แต่มันกลับไม่ได้คาดหวัง["aa","bb","c","g"] ["aa","bb"]ในที่สุดฉันก็วางแผนที่จะทำมันให้เสร็จnubแต่ฉันกำลังดิ้นรนกับการหาส่วน innerJoin

แก้ไข:

ขอบคุณคำตอบด้านล่างนี่คือวิธีแก้ปัญหา:

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

lookupฟังก์ชั่นที่คุณต้องการสำหรับเรื่องนี้คือ ตัวอย่างเช่น:

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

ฟังก์ชั่นอื่น ๆ ซึ่งจะเป็นประโยชน์ที่นี่ก็คือData.Maybe.catMaybesถ้าคุณมีรายการเหมือน[Just 1, Just 2, Nothing, Just 3, Nothing]และนำไปใช้กับมันคุณจะได้รับcatMaybes [1, 2, 3]ดังนั้นคุณก็สามารถรวมlookupและcatMaybesที่จะได้รับcatMaybes $ map (flip lookup dict) list1เป็นวิธีแก้ปัญหาที่คุณต้องการ การปรับแต่งเพิ่มเติมคือการสังเกตว่าData.MaybeนิยามmapMaybe f xsว่าเทียบเท่าcatMaybe (map f xs)ดังนั้นคุณสามารถลดความซับซ้อนลงไปmapMaybe (flip lookup dict) list1ได้