CODEWITHSUNDEEP
clojure
Erica Maine
Erica Maine

Reputation: 147

How to delete an element from a nested list?

I have a deeply nested list and I want to delete a given element from all its occurrences in the list. I have this code:

(defn eliminate [value lst]
            (defn sub-eliminate [lst]
              (def currentItem (first lst))
              (if-not (empty? lst)
                (if (seq? currentItem)
                  (cons (sub-eliminate currentItem) (sub-eliminate (rest lst)))
                  (if (= value currentItem)
                    (sub-eliminate (rest lst))
                    (cons currentItem (sub-eliminate (rest lst)))
                    )
                  )
                '()
                )
              )
              (sub-eliminate lst)
            )

But, it doesn't delete at inner levels. Why??

Upvotes: 3

Views: 284

Answers (3)

overthink
overthink

Reputation: 24463

(defn expel [victim xs] 
  (mapcat (fn [x]
            (cond
              (sequential? x) [(expel victim x)]
              (= x victim) [] 
              :else [x])) 
          xs))

Upvotes: 2

Thumbnail
Thumbnail

Reputation: 13483

My guess is that you're using vectors as sequences. 

(eliminate 3 [3 3])
;()

(eliminate 3 [3 [3]])
;([3])

This would have been trivial to find had you shown us an example: tut, tut!

What's going on?

Although vectors are seqable, they are not sequences:

(seq? [])
;false

At the outer level, you treat lst as a sequence, so first and rest work, since they wrap their argument in an implicit seq. But seq? will fail on any immediately enclosed vector, and those further in won't even be seen.

If you replace seq? with sequential?, lists and vectors will work. 

(sequential? [])
;true

More serious, as @noisesmith noted, is your use of def and defn at inner scope. Replace them with let or letfn.

You could also improve your style:

  1. Replace (if-not (empty? lst) ... ) with (if (seq lst) ...).
  2. Use cond to flatten your nested ifs. This requires inverting the test in (1), so removes the need for it.
  3. Use recur for the tail-recursive case where you find value, as @Mark does.

If you don't want to see the result, look away now: 

(defn eliminate [value lst]
  (letfn [(sub-eliminate [lst]
            (let [current-item (first lst)]
              (cond
               (empty? lst) '()
               (sequential? current-item) (cons (sub-eliminate current-item) 
                                                (sub-eliminate (rest lst)))
               (= value current-item) (recur (rest lst))
               :else (cons current-item (sub-eliminate (rest lst))))))]
    (sub-eliminate lst)))

There is a remaining tender spot:

  • You invoke (first lst) before you know that lst is not empty. No harm done: you'll just get nil, which you ignore.

An Alternative Apporach using Destructuring

You can often use destructuring to abbreviate recursive processing of sequences. I'd be inclined to express your function thus: 

(defn eliminate [x xs]
  ((fn rem-x [xs]
     (if-let [[y & ys] (seq xs)]
       (if (= x y)
         (recur ys)
         (cons
          (if (sequential? y) (rem-x y) y)
          (rem-x ys)))
       ()))
   xs))

Upvotes: 3

Mark Karpov
Mark Karpov

Reputation: 7599

For the sake of learning take a look at this function:

(define rember*
  (lambda (x l)
    (cond ((null? l) '())
          ((atom? (car l))
          (if (eq? (car l) x)
              (rember* x (cdr l))
              (cons (car l)
                    (rember* x (cdr l)))))
          (else (cons (rember* x (car l))
                      (rember* x (cdr l)))))))

This is a simple recursive function from book 'The Little Schemer', which is a good source to learn how to write such recursive functions.

Let's see if we can translate it into Clojure:

(defn rember* [x l]
  (cond (empty? l) '()
        (seq? (first l)) (cons (rember* x (first l))
                               (rember* x (rest l)))
        :else (if (= (first l) x)
                (recur x (rest l))
                (cons (first l)
                      (rember* x (rest l))))))


user> (rember* 'x '((x y) x (z (((((x))))))))
;; => ((y) (z ((((()))))))

Upvotes: 2

Related Questions