haskell - 如何通过 Haskell 中的自引用键删除列表的一部分

Question

我有一个这种类型的列表:[(a, [a])]。例如:

[("a",["x","y"]),("x",["a","y"]),("z",[]),("y",["a","x"])]

我想过滤这个列表。过滤应该像这样工作:

1. 从第一项开始，遍历第一个元组的项
2. 删除第一个元组中的键(因此删除 "x"、"y")

最终结果应该变成:

[("a",["x","y"]),("z",[])] -- the "x" and "y" are removed because they live in "a"

想法是获取一个列表，然后在该列表上应用Map.delete from import qualified Data.Map as Map。但是，当引入 Maybe 时，我会陷入困境。这是我的代码:

import System.IO
import Data.Maybe as Maybe
import qualified Data.Map as Map


list = [("a",["x","y"]),("x",["a","y"]),("z",[]),("y",["a","x"])]
    
main :: IO ()
main = do
    let myMap = Map.fromList list
    let myList = funcA list myMap 
    print myList
    
funcA (x:xs) myMap
   | f == Nothing = Nothing
--   | otherwise = f
--   | otherwise = funcC f myMap
   | otherwise = Maybe.maybeToList f
    where a = fst x
          f = funcB a myMap

funcB key myMap = Map.lookup key myMap

funcC portion myMap = portion

你能帮帮我吗？

----------------编辑

回答后代码将如下所示:

import System.IO
import Data.Maybe as Maybe
import qualified Data.Map as Map


list = [("a",["x","y"]),("x",["a","y"]),("z",[]),("y",["a","x"])]
    
main :: IO ()
main = do
    let myList = removeKeys list
    print myList


removeKeys :: Eq a => [(a, [a])] -> [(a, [a])]
removeKeys [] = []
removeKeys (kv@(_, vs): kvs) = kv : removeKeys (filter ((`notElem` vs). fst) kvs)

输出:

> runghc program
[("a",["x","y"]),("z",[])]

我喜欢回答的解决方案，因为使用了创造性的方式 filter。它基本上是这样做的:

Prelude> let vs = ["x","y"]
Prelude> let kvs = [("x",["a","y"]),("z",[]),("y",["a","x"])]
Prelude> filter ((`notElem` vs). fst) kvs
[("z",[])]

Answer 1

您可以创建一个递归函数，用二元组的第二项中的项过滤列表的其余部分，因此:

removeKeys :: Eq a => [(a, [a])] -> [(a, [a])]
removeKeys [] = []
removeKeys (kv@(_, vs): kvs) = kv : removeKeys (filter (<strong>(`notElem` vs). fst</strong>) kvs)

将不考虑删除项目的键值对中的值中的项目。因此，如果 "x" 例如有 ("x", ["a", "y", "z"])，它不会删除 "z"，因为它位于已删除的项目中。