CODEWITHSUNDEEP
haskellfunctional-programminglist-comprehension
Saurabh Nanda
Saurabh Nanda

Reputation: 6793

How to delete from list, return the deleted element, and return the "modified" list

(Newbie alert)

I'm trying to write a function with the following signature, because I couldn't find something similar in the standard libraries:

deleteFromList :: (b -> a -> Bool) -> b -> [a] -> (Maybe a, [a])

-- Example 1: Item found in the list, and deleted
deleteFromList (\(id1, name1), (id2, name2) -> id1==id2) 3 [(1, "Jack"), (2, "Jill"), (3, "Joe"), (4, "Jimmy")]
-- returns (Just (3, "Joe"), [(1, "Jack"), (2, "Jill"), (4, "Jimmy")]

-- Example 2: Item not found in list
deleteFromList (\(id1, name1), (id2, name2) -> id1==id2) 5 [(1, "Jack"), (2, "Jill"), (3, "Joe"), (4, "Jimmy")]
-- returns (Nothing, [(1, "Jack"), (2, "Jill"), (3, "Joe"), (4, "Jimmy")]

I know this can probably be written by calling Data.List.find and Data.List.deleteBy, but that would result in two traversals of the list. I want to make my life tougher and do this in just a single traversal.

Upvotes: 1

Views: 127

Answers (3)

Zacharie 007
Zacharie 007

Reputation: 126

@Mark Seemann nice job, as Chi has suggested, it's better to improve with partition 

  Prelude DL> let myFunction x = partition ((==x).(fst))

Examples:

  Prelude DL> myFunction  1 [(1,2),(2,9)]
  ([(1,2)],[(2,9)])
  Prelude DL> myFunction  5 [(1, "Jack"), (2, "Jill"), (3, "Joe"),(4, "Jimmy")]
  ([],[(1,"Jack"),(2,"Jill"),(3,"Joe"),(4,"Jimmy")])
  Prelude DL> myFunction  3 [(1, "Jack"), (2, "Jill"), (3, "Joe"),(4, "Jimmy")]
  ([(3,"Joe")],[(1,"Jack"),(2,"Jill"),(4,"Jimmy")])

This is more general:

  Prelude> let myFunction g  x = partition (g .fst)
  Prelude> myFunction (==3) 3 [(1, "Jack"), (2, "Jill"), (3, "Joe"),(4, "Jimmy")]
  ([(3,"Joe")],[(1,"Jack"),(2,"Jill"),(4,"Jimmy")])

Upvotes: 1

denys.fridman
denys.fridman

Reputation: 165

A simple recursive solution:

deleteFromList :: (b -> a -> Bool) -> b -> [a] -> (Maybe a, [a])
deleteFromList p b (x: xs) | p b x     = (Just x, xs)
                           | otherwise = let (y, rest) = deleteFromList p b xs in
                                           (y, x: rest)
deleteFromList _ _ [] = (Nothing, [])

Upvotes: 1

Mark Seemann
Mark Seemann

Reputation: 233150

You can implement that function fairly easily with foldr, like this:

deleteFromList :: (b -> a -> Bool) -> b -> [a] -> (Maybe a, [a])
deleteFromList p target = foldr folder (Nothing, [])
  where
    folder x (Nothing, xs) | p target x = (Just x, xs)
    folder x (m, xs)                    = (m, x : xs)

although I'm sure that experienced Haskellers (which I'm not) will be able to come up with a one-liner...

Examples of usage:

*Q35115395> deleteFromList (\x y -> x == fst y) 3 [(1, "Jack"), (2, "Jill"), (3, "Joe"), (4, "Jimmy")]
(Just (3,"Joe"),[(1,"Jack"),(2,"Jill"),(4,"Jimmy")])

*Q35115395> deleteFromList (\x y -> x == fst y) 5 [(1, "Jack"), (2, "Jill"), (3, "Joe"), (4, "Jimmy")]
(Nothing,[(1,"Jack"),(2,"Jill"),(3,"Joe"),(4,"Jimmy")])

Upvotes: 2

Related Questions