'How to remove portions of a list by self referencing keys in Haskell
I have a list with this type: [(a, [a])].
For example:
[("a",["x","y"]),("x",["a","y"]),("z",[]),("y",["a","x"])]
I would like to filter this list. The filtering should work like this:
- start at first item, traverse items from first tuple
- remove keys that are in the first tuple (so remove
"x","y")
End result should become:
[("a",["x","y"]),("z",[])] -- the "x" and "y" are removed because they live in "a"
The idea is to get a list and then to apply Map.delete from import qualified Data.Map as Map on that list. However, I'm stuck on the things when Maybe is introduced. This is my code:
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
Can you help me out?
-------------- edit
After answering the code will look like this:
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)
Output:
> runghc program
[("a",["x","y"]),("z",[])]
I like the answered solution because of the creative way filter was used. It is basically doing this:
Prelude> let vs = ["x","y"]
Prelude> let kvs = [("x",["a","y"]),("z",[]),("y",["a","x"])]
Prelude> filter ((`notElem` vs). fst) kvs
[("z",[])]
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
