Haskell. INNER JOIN của hai danh sách

Question

Tôi đã hỏi google và cố gắng tìm các công cụ cần thiết để thực hiện việc này, nhưng dường như không thể tìm ra giải pháp cho vấn đề của tôi. Toàn bộ nhiệm vụ là sử dụng từ điển để dịch một danh sách và chỉ giữ lại các giá trị duy nhất. Ví dụ các đầu vào sau:

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

được cho là mang lại kết quả sau:

result = ['aa', 'bb']

Đây là nơi tôi bị mắc kẹt cho đến nay:

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)

cái nào mang lại

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

Vì vậy, để giải quyết vấn đề này, tôi đã nghĩ rằng có thể có một cách sử dụng filterhoặc maphoặc foldlmột cách nào đó để thực hiện một phép nối bên trong như sau:

let result = innerJoin values result

Hiện tại tôi có một cái gì đó giống như sau:

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)

Nhưng nó trở lại ["aa","bb","c","g"]và không như mong đợi ["aa","bb"]. Cuối cùng, tôi dự định hoàn thành nó nub, nhưng tôi đang đấu tranh với việc tìm ra phần nội tâm.

BIÊN TẬP:

Nhờ câu trả lời dưới đây là giải pháp cho vấn đề:

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

Chức năng bạn muốn cho điều này là lookup. Ví dụ:

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

Chức năng hữu ích khác ở đây là Data.Maybe.catMaybes: nếu bạn có một danh sách thích [Just 1, Just 2, Nothing, Just 3, Nothing]và áp dụng catMaybescho nó, bạn sẽ nhận được [1, 2, 3]. Vì vậy, bạn có thể chỉ cần kết hợp lookupvà catMaybesđể có được catMaybes $ map (flip lookup dict) list1giải pháp mong muốn của bạn. Một cải tiến bổ sung cần lưu ý rằng Data.Maybeđịnh nghĩa mapMaybe f xslà tương đương với catMaybe (map f xs), vì vậy bạn có thể đơn giản hóa điều đó xuống mapMaybe (flip lookup dict) list1.