This is the fifth Chapter of a series of posts about porting The Little Schemer to Clojure. You may wish to read the intro.

Ok – so far we’ve introduced lists [Ch1], we’ve pulled things out of lists [Ch2], we’ve built lists [Ch3] and we’ve assembled a minimal numeric tower[Ch4]. The assumption behind all of these was that we were only reading or making one change at a time. This time we’ll extend our capabilities to handle multiple items. To put it another way – this chapter is all about the ‘find all’ and the ‘replace all’.

We’ll start with some revision – we’ll go back to our old friend member.

(def member?
  (fn [a lat]
    (cond
      (null? lat) false
      true (or
        (= (first lat) a)
        (member? a (rest lat)))) ))

(println (member? 'sweet '(potato wedges with sweet chilli sauce))) ; //=> true
(println (member? 'sweet '(potato wedges with sweet sweet chilli sauce))) ; //=> true

Now the particular point we’re looking at now is that this function will stop at the first occurrence of a in lat. Now we’ll go back to another old friend rember.

(def rember
  (fn [ a lat]
    (cond
      (null? lat) '()
      true (cond
        (= (first lat) a) (rest lat)
        true (cons (first lat)
          (rember
            a (rest lat)))))))

(println (rember 'banana '(apple banana orange))) ; //=> (apple orange)
(println (rember 'banana '(apple banana banana orange))); //=> (apple banana orange)

Again – the point was that only the first occurrence is dealt with – this chapter is about how we will to address that. So let’s start with multirember:

(def multirember
  (fn [a lat]
    (cond
      (null? lat) '()
      true (cond
             (= (first lat) a) (multirember a (rest lat))
             true (cons (first lat) (multirember a (rest lat)))))))

(println (multirember 'sweet '(potato wedges with sweet sweet chilli sauce))); //=> (potato wedges with chilli sauce)

The main difference is that we keep calling the function until the end of the lat, even if the result is found.

Now let’s do multiinsertR:

(def multiinsertR
  (fn [new old lat]
    (cond
      (null? lat) '()
      true (cond
             (= (first lat) old) (cons (first lat) (cons new (multiinsertR new old (rest lat))))
             true (cons (first lat) (multiinsertR new old (rest lat)))))))

(println (multiinsertR 'hot 'with '(with potato wedges with chilli sauce))); //=> (with hot potato wedges with hot chilli sauce)

Too easy! Now let’s do multiinsertL:

(def multiinsertL
  (fn [new old lat]
    (cond
      (null? lat) '()
      true (cond
             (= (first lat) old) (cons new (cons old (multiinsertL new old (rest lat))))
             true (cons (first lat) (multiinsertL new old (rest lat)))))))

(println (multiinsertL 'with 'hot '(hot potato wedges hot chilli sauce))); //=> (with hot potato wedges with hot chilli sauce)

So a pattern is developing here – which means it’s time for another Commandment. Here Goes. The Sixth commandment states that you Always change at least one argument while recurring. The changing argument(s) should be tested in the termination condition(s) and it should be changed to be closer to termination. For example:
when using rest, test termination with empty?
when using sub1, test termination with zero?

Ok – so apart from knowing the principles to have confidence in writing recursive code in the future – why else is this relevant? It’s important for building more complex data structures. One of Clojure’s key strengths is that it has lazy functional data structures. Clojure’s data structures are built around this idea of hash-trie. It’s the idea that you can modify a tree structure that is still immutable and performant. The point being – you need to start building blocks for how you think about data structures.

Now we’re going to look at multisubst:

(def multisubst
  (fn [new old lat]
    (cond
      (null? lat) '()
      true (cond
             (= (first lat) old) (cons new (multisubst new old (rest lat)))
             true (cons (first lat) (multisubst new old (rest lat)))))))

(println (multisubst 'hot 'sweet '(sweet potato wedges with sweet chilli sauce))); //=> (hot potato wedges with hot chilli sauce)

Now we’re going to do occur which is a bit like the aggregate count function in sql.

(def occur
  (fn [a lat]
    (cond
      (null? lat) 0
      true (cond
             (= (first lat) a) (add1 (occur a (rest lat)))
             true (occur a (rest lat))))))

(println (occur 'hot '(potato wedges with hot hot hot chilli sauce))); //=> 3

This chapter ends strangely – we digress into an optimisation of the rempick function by adding a new primitive one?:

(def one?
  (fn [n]
    (= n 1)))

(def rempick
  (fn [n lat]
    (cond
      (null? lat) '()
      (one? n) (rest lat)
      true (cons (first lat) (rempick (sub1 n) (rest lat))))))

(println (rempick 4 '(potato wedges with hot chilli sauce))); //=> (potato wedges with chilli sauce)

You can see it running here.

Conclusion
Here we’ve adapted our existing functions to be able to work for multiple occurrences of the search result. We’ve added one new primitive function: one? 

In total our primitives so far are: atom?, null?, first, rest, cond, fn, def, empty?,=, cons, add1, sub1 and one?. These are all the functions (and those in the chapters to come) that we’ll need to implement to get our metacircular interpreter working.

Bringing it Back to Clojure

So how do we do a multirember in Clojure normally? Here is an online example:

(remove #{:foo} #{:foo :bar})      ;// => (:bar)
(remove #{:foo} [:foo :bar])       ;// => (:bar)
(remove #{:foo} (list :foo :bar))  ;// => (:bar)

Other functions that apply to other data structures to consider:

(disj #{:foo :bar} :foo)       ;// => #{:bar}
(dissoc {:foo 1 :bar 2} :foo)  ;// => {:bar 2}
(pop [:bar :foo])              ;// => [:bar]
(pop (list :foo :bar))         ;// => (:bar)

So how is remove implemented in Clojure?

(defn remove
  [pred coll]
  (filter (complement pred) coll))

This is more concise – but requires knowledge of the filter and complement functions – which we’ve chosen to exclude to keep a simple set of primitives.