Remove elements in list with a list of Int (Haskell)

Question

I am writing function that take a list of Int, a list of general type a and remove all elements that have index in the list of Int.

For example: removeEl [1,3,4] [1,2,3,4,5,6] return [1,3,6] or removeEl [1,2] "Firefox" return "Fefox"

Here is my attempt:

removeEl :: [Int] -> [a] -> [a]
removeEl [] xs = []
removeEl ns [] = []
removeEl (n:ns) (x:xs) | n == 0 = removeEl ns xs
                       | n > 0 = x:removeEl (n-1) xs

I realize (n-1) is an Int, not [Int] so it fail. Do I need to write an auxiliary function to use?

In the n > 0 case, you would also need to decrease the following indices (not just the first). — C-Otto
– C-Otto, Commented Sep 8, 2016 at 13:51

chepner · Accepted Answer · 2016-09-09 04:10:27Z

3

You need to pass a new list, but every item in that list needs to be decremented, because you've shifted the positions of every element of the second argument. This is true whether or not you've actually removed the head element.

removeEl (n:ns) (x:xs) | n == 0 = removeEl (map pred ns) xs
                       | n > 0 = x:removeEl (map pred (n:ns)) xs

There's a lot of opportunity to refactor this, but nothing I've played with feels significantly simpler.

Also, your first base case is wrong: with no items in the index list, you want to return everything, not nothing:

remove [] xs = xs

(Keep in mind this only works if the first argument is monotonically increasing.)

You can also avoid the explicit recursion with a list comprehension:

removeEl ns xs = [x | (n,x) <- zip [0..] xs, not(n `elem` ns)]

edited Sep 9, 2016 at 4:10

answered Sep 8, 2016 at 13:51

chepner

538k77 gold badges594 silver badges746 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

GlossMash Over a year ago

I tried you code but it says No instance for (Num (Int -> Int)) in the first argument of map, the error is at line of case n==0

chepner Over a year ago

Because I still forget that negative literals are a pain in Haskell.

user1747134 Over a year ago

One could also simplify it a bit by using pred instead of subtract 1

chepner Over a year ago

Ah, I forgot about pred.

user2297560 · Accepted Answer · 2016-09-08 15:08:44Z

3

I believe your algorithm is O(n*m), where n is the number of elements in the list and m is the number of indices to remove. It also has the unfortunate requirement that the list of indices must be ordered. Here's a ~O(n*log(m)) solution that doesn't require the indices be ordered.

import qualified Data.Set as Set

removeE1 indices xs = go 0 xs
  where is = Set.fromList indices
        go _ [] = []
        go n (y:ys) | n `Set.member` is = go (n+1) ys
                    | otherwise         = y : go (n+1) ys

And this could be improved a bit by using a hash map.

edited Sep 8, 2016 at 15:08

answered Sep 8, 2016 at 15:02

user2297560

2,9931 gold badge16 silver badges11 bronze badges

Collectives™ on Stack Overflow

Remove elements in list with a list of Int (Haskell)

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related