# One Function to rule them all

## Fork this

https://github.com/iloveponies/one-function-to-rule-them-all

## Return of the recursion

Often you want to combine elements of a collection, like calculate the sum or product of a list of numbers, or concatenate a list of strings. That is, we want to make a transformation like this:

```
(cons 1 (cons 2 (cons 3 nil)))
;=> (+ 1 (+ 2 (+ 3 0)))
```

Or like this:

```
(cons 1 (cons 2 (cons 3 nil)))
;=> (* 1 (* 2 (* 3 0)))
```

Our tool for this job was recursion:

```
(defn sum [a-seq]
(if (empty? a-seq)
0
(+ (first a-seq) (sum (rest a-seq)))))
```

To make this more efficient, we made this tail recursive using `recur`

and an accumulator:

```
(defn sum [a-seq]
(let [sum-helper (fn [acc a-seq]
(if (empty? a-seq)
acc
(recur (+ acc (first a-seq))
(rest a-seq))))]
(sum-helper 0 a-seq)))
```

This iterative `sum`

would evaluate like this:

```
;function evaluation accumulator value
(sum (cons 1 (cons 2 (cons 3 (cons 4 nil))))) ;
;=> (sum-helper 0 (cons 1 (cons 2 (cons 3 (cons 4 nil))))) ; 0
;=> (sum-helper 1 (cons 2 (cons 3 (cons 4 nil)))) ; (+ 0 1) => 1
;=> (sum-helper 3 (cons 3 (cons 4 nil))) ; (+ 1 2) => 3
;=> (sum-helper 6 (cons 4 nil)) ; (+ 3 3) => 6
;=> (sum-helper 10 nil) ; (+ 6 4) => 10
;=> 10
```

Now lets say that we would like to compute the product of a list of numbers. It would go like this:

```
(defn product [a-seq]
(let [product-helper (fn [acc a-seq]
(if (empty? a-seq)
acc
(recur (* acc (first a-seq))
(rest a-seq))))]
(product-helper 1 a-seq)))
```

The only two things that changed was the function `+`

that was replaced with `*`

and the initial value `0`

that was replaced by `1`

. So one starts to wonder if there is a pattern behind this all. And it turns out that there is. A function called `reduce`

.

`(reduce combining-function initial-accumulator-value a-sequence)`

takes:

- a function that is used to combine the current accumulator value and the current element of the parameter sequence
- an initial value for the accumulator
- a sequence

So what do we get if we re-define our `sum`

and `product`

with `reduce`

?

```
(defn sum [a-seq]
(reduce + 0 a-seq))
(defn product [a-seq]
(reduce * 1 a-seq))
```

Let’s see how this `sum`

would evaluate:

```
(sum (cons 4 (cons 7 (cons 2 nil))))
;=> (reduce + 0 (cons 4 (cons 7 (cons 2 nil))))
;=> (reduce + (+ 0 4) (cons 7 (cons 2 nil))) ; accumulator: 0, element: 4
;=> (reduce + 4 (cons 7 (cons 2 nil))) ; (+ 0 4) => 4
;=> (reduce + (+ 4 7) (cons 2 nil)) ; accumulator: 4, element: 7
;=> (reduce + 11 (cons 2 nil)) ; (+ 4 7) => 11
;=> (reduce + (+ 11 2) nil) ; accumulator: 11, element: 2
;=> (reduce + 13 nil) ; (+ 11 2) => 13
;=> 13 ; accumulator: 13
```

So `reduce`

managed to abstract out just the two things that where different in `sum`

and `product`

. The initial value and the operation that composes the values into a one value. Everything else seems to be handled by `reduce`

. So how does it work?

```
(defn reduce [f initial a-seq]
(if (empty? a-seq)
initial
(recur f
(f initial (first a-seq))
(rest a-seq))))
```

Lets go through an evaluation of `reduce`

:

```
(reduce + 0 [1 2 3])
;=> (reduce + (+ 0 1) [2 3])
;=> (reduce + (+ (+ 0 1) 2) [3])
;=> (reduce + (+ (+ (+ 0 1) 2) 3) [])
;=> (+ (+ (+ 0 1) 2) 3)
;=> 6
```

Time to put the good tool to use.

### Exercise 1

Write the function `(concat-elements a-seq)`

that takes a sequence of sequences and concatenates them together with `concat`

.

Don’t use `apply`

to implement this function.

```
(concat-elements []) ;=> ()
(concat-elements [[1 2]]) ;=> (1 2)
(concat-elements [[1 2] [3 4]]) ;=> (1 2 3 4)
```

## Two Sides of a Coin

One can call `reduce`

in two different ways:

`(reduce combinator-function initial-accumulator-value input-sequence)`

or

`(reduce combinator-function input-sequence)`

If `input-sequence`

is not empty, then the second form works like this:

```
(reduce f (cons elem rest-of-seq))
;=> (reduce f elem rest-of-seq)
```

that is, it uses the first element of the parameter sequence as the initial accumulator value.

And if `input-sequence`

is empty, then:

- The first form just returns
`initial-accumulator-value`

- The second form returns
`(combinator-function)`

, that is, it calls`combinator-function`

with zero parameters.

Let’s try this version without initial value:

```
(defn seq-min [a-seq]
(reduce min a-seq))
(seq-min [1]) => 1
(seq-min [5 3 2 6]) => 2
(seq-min [])
=> java.lang.IllegalArgumentException:
Wrong number of args (0) passed to: core$min (NO_SOURCE_FILE:0)
```

Now the call with empty sequence results in an exception, since `min`

is not defined for 0 arguments. Since `seq-min`

used `reduce`

without an initial value, it called `(min)`

when it was given an empty sequence.

Lets look at an evaluation of a `reduce`

call without an initial value.

```
(seq-min [5 3 2 6])
;=> (reduce min [5 3 2 6])
;=> (reduce min 5 [3 2 6]) ; Use the first element as the initial value
;=> (reduce min (min 5 3) [2 6])
;=> (reduce min 3 [2 6])
;=> (reduce min (min 3 2) [6])
;=> (reduce min 2 [6])
;=> (reduce min (min 2 6) [])
;=> (reduce min 2 [])
;=> 2
```

### Exercise 2

Write the function `(str-cat a-seq)`

that takes a sequence of strings and catenates them with one space character between each.

```
(str-cat ["I" "am" "Legend"]) ;=> "I am Legend"
(str-cat ["I" "am" "back"]) ;=> "I am back"
(str-cat ["more" " " "space"]) ;=> "more space"
(str-cat []) ;=> ""
```

You probably want to handle the special case of empty parameter outside reduce.
### Exercise 3

Write the function `(my-interpose x a-seq)`

that places `x`

between every element of `a-seq`

.

Keep in mind how `conj`

works for vectors.

```
(my-interpose 0 [1 2 3]) ;=> (1 0 2 0 3)
(my-interpose "," ["I" "me" "myself"]) ;=> ("I" "," "me" "," "myself")
(my-interpose :a [1]) ;=> (1)
(my-interpose :a []) ;=> ()
```

Let’s look at another example. We implemented the function `count-elem`

in Recursion, which counts the occurrences of an element in a sequence. Let’s reimplement that function with reduce:

```
(defn count-elem [elem a-seq]
(let [counter (fn [count e]
(if (= e elem)
(inc count)
count))]
(reduce counter 0 a-seq)))
```

```
(count-elem :D [13 "\o/" :D :$ :D [:D] :< "~^._.^~"])
;=> (reduce counter 0 [13 "\o/" :D :$ :D [:D] :< "~^._.^~"])
;=> (reduce counter (counter 0 13) ["\o/" :D :$ :D [:D] :< "~^._.^~"])
;=> (reduce counter 0 ["\o/" :D :$ :D [:D] :< "~^._.^~"])
;=> (reduce counter (counter 0 "\o/") [:D :$ :D [:D] :< "~^._.^~"])
;=> (reduce counter 0 [:D :$ :D [:D] :< "~^._.^~"])
;=> (reduce counter (counter 0 :D) [:$ :D [:D] :< "~^._.^~"])
;=> (reduce counter 1 [:$ :D [:D] :< "~^._.^~"])
;=> (reduce counter (counter 1 :$) [:D [:D] :< "~^._.^~"])
;=> (reduce counter 1 [:D [:D] :< "~^._.^~"])
;=> (reduce counter (counter 1 :D) [[:D] :< "~^._.^~"])
;=> (reduce counter 2 [[:D] :< "~^._.^~"])
;=> (reduce counter (counter 2 [:D]) [:< "~^._.^~"])
;=> (reduce counter 2 [:< "~^._.^~"])
;=> (reduce counter (counter 2 :<) ["~^._.^~"])
;=> (reduce counter 2 ["~^._.^~"])
;=> (reduce counter (counter 2 "~^._.^~") [])
;=> (reduce counter 2 [])
;=> 2
```

### Exercise 4

Write the function `(my-count a-seq)`

that returns the length of a sequence.

Do not use `count`

in your implementation.

```
(my-count []) ;=> 0
(my-count [1 2 3]) ;=> 3
(my-count [1]) ;=> 1
```

### Exercise 5

Write the function `(my-reverse a-seq)`

that reverses a sequence.

```
(my-reverse [1 2 3]) ;=> (3 2 1)
(my-reverse [1 2]) ;=> (2 1)
(my-reverse []) ;=> ()
```

### Exercise 6

Write the function `(min-max-element a-seq)`

that returns the maximal and minimal elements of `a-seq`

in a vertor like `[min max]`

.

```
(min-max-element [2 7 3 15 4]) ;=> [2 15]
(min-max-element [1 2 3 4]) ;=> [1 4]
(min-max-element [1]) ;=> [1 1]
```

### Exercise 7

Write the function `(insert sorted-seq n)`

that adds the number `n`

into a sorted sequence of number. The ordering of the sequence must be preserved.

You don’t need to use `reduce`

for this, and you probably don’t want to.

```
(insert [] 2) ;=> (2)
(insert [1 3 4] 2) ;=> (1 2 3 4)
(insert [1] 2) ;=> (1 2)
```

Now implement `(insertion-sort a-seq)`

using `reduce`

and the function `insert`

.

```
(insertion-sort [2 5 3 1]) ;=> (1 2 3 5)
(insertion-sort [1 2]) ;=> (1 2)
```

### Exercise 8

Write the fuction `(parity a-seq)`

that picks into a set those elements of `a-seq`

that occur odd number of time.

```
(parity [:a :b :c]) ;=> #{:a :b :c}
(parity [:a :a :b :b]) ;=> #{}
(parity [1 2 3 1]) ;=> #{2 3}
```

## Var…argghhhh!

As you may have noticed, some functions in Clojure can take variable amount of parameters.

```
(+ 1 1) ;=> 2
(+ 1 1 1 1 1) ;=> 5
```

Not surprisingly, one can define such functions themselve.

```
(defn one-or-two
([x] 1)
([x y] 2))
```

This function has two separate definitions. Each definition is separated from the others by enclosing it in parentheses. Each of the definitions takes a different amount of parameters. This is called *arity overloading*. In English, the right definition is chosen based on how many parameters were given to the function. This function can be called with one or two parameters.

```
(one-or-two :a) ;=> 1
(one-or-two 5 6) ;=> 2
(one-or-two 1 2 3)
;=> ArityException
; Wrong number of args (3) passed to: user$one-or-two
; clojure.lang.AFn.throwArity (AFn.java:437)
```

### Exercise 9

Write the function `minus`

that takes one or two parameters.

- If given a one parameter \(x\), it returns \(-x\).
- If given to parameters \(x\) and \(y\), it returns \(x - y\).

```
(minus 2) ;=> -2
(minus 4 3) ;=> 1
```

But what if you don’t know the amount of parameters given before hand? Lets look at a definition of `max`

:

```
(defn max
([x] x) ; one parameter
([x y] (if (> x y) x y)) ; two parameters
([x y & more] ; more than two parameters
(reduce max (max x y) more)))
```

First of all, the function has three separate definitions. If we call the function with one or two parameters, the first and second definitions are used, respectively.

The third definition of `max`

is using *variable arguments*. It means that the function can be called with any amount of parameters. The first two parameters are given names `x`

and `y`

and the rest of the parameters are grouped into a sequence and given a name `more`

. Lets look at an evaluation:

```
(max 1 2 3 4)
;=> (reduce max (max 1 2) '(3 4))
;=> (reduce max 2 '(3 4))
;=> (reduce max (max 2 3) '(4))
;=> (reduce max 3 '(4))
;=> (reduce max (max 3 4) '())
;=> (reduce max 4 '())
;=> 4
```

### Exercise 10

Write the function `count-params`

that accepts any number of parameters and returns how many it was called with. You need only a one definition for this.

```
(count-params) ;=> 0
(count-params :a) ;=> 1
(count-params :a 1 :b :c) ;=> 4
```

### Exercise 11

Write the function `my-*`

that takes any number of parameters.

- If no parameters are given, return 1
- If one parameter \(x\) is given, return \(x\).
- If two parameters \(x\) and \(y\) are given, return \(xy\).
- If more than two parameters \(x\), \(y\), \(\dots\) are given, return their product \(x \cdot y \cdots\).

You are free to use `*`

, but not `apply`

.

```
(my-*) ;=> 1
(my-* 4 3) ;=> 12
(my-* 1 2 3 4 5) ;=> 120
```

### Exercise 12

Remember the function `pred-and`

that you implemented in Predicates? Write a new definition for it that works for any amount of parameters.

- If no parameters are given, return a predicate that always returns
`true`

. - If only one predicate
`p`

is given, return`p`

. - If two predicates are given, return a predicate that returns
`true`

if both of them return`true`

and`false`

otherwise. - If more than two predicates are given, return a predicate that returns
`true`

only if all of the predicates return`true`

and`false`

otherwise.

```
(filter (pred-and) [1 0 -2]) ;=> (1 0 -2)
(filter (pred-and pos? odd?) [1 2 -4 0 6 7 -3]) ;=> (1 7)
(filter (pred-and number? integer? pos? even?)
[1 0 -2 :a 7 "a" 2]) ;=> (0 2)
```

## Encore

The next exercise is a bit trickier.

### Exercise 13

3 points

Write the function `my-map`

that works just like standard `map`

. It takes one or more sequences and a function `f`

that takes as many parameters as there are sequences.

```
(my-map inc [1 2 3 4]) ;=> (2 3 4 5)
(my-map + [1 1 1] [1 1 1] [1 1 1]) ;=> (3 3 3)
(my-map vector [1 2 3] [1 2 3] [1 2 3]) ;=> ((1 1 1) (2 2 2) (3 3 3))
```