{:check ["true"], :rank ["map" "filter" "reduce"]}

Index

Functional Programming with Sequences

In this section, we will further explore higher order functions and see how functions can be used to capture different iteration patterns to transform sequences.

Map

Map is one of the most popular higher order functions. Some version of map is available in other languages including: Python, Java (stream API), Javascript.

Map unary function to a sequence

Suppose we have a function f that maps values to values.
```
     o
     |
     | f
     |
     v
     x
```

map is a higher order function that applies f to every element in an input sequence.

(map f seq)

; f is a function
; seq is a sequence of input elements 
; (map f seq) returns an output sequence

We can illustrate it with a digram.

    ( o   o   o   o   o   o )   seq
      |   |   |   |   |   |
      |   |   |   |   |   | f
      |   |   |   |   |   |
    ( x   x   x   x   x   x )   (map f seq)

Mapping a function with two parameters over two sequences

map can accept multiple input sequences if f has multiple parameters.

(map f seq1 seq2)

; seq1 - first sequence, x's
; seq2 - second sequence, y's
; (f x y) - function with two parameters
; returns the output of f on corresponding x's and y's from sequences

The action of (map f seq1 seq2) is as follows:

      (     *        *       *       *  ) seq2
seq1  ( o   |    o   |   o   |   o   |  ) 
        |   |    |   |   |   |   |   | 
         \ /      \ /     \ /     \ / 
      (   +        +       +       +    )   (map f seq1 seq2)

Map-index

(map-indexed f seq-in`` provides the function f` with the index position of the input element. So the function must be expecting an integer as its first argument.
```
(map-indexed f seq-in)
; (f i x):  i is the position 0, 1, 2, 3 ..., and x the element
; seq-in: the input sequeneces
; returns the output sequence
```

The action is shown as:

   (     o       o       o        o ) seq-in
   ( 0   |   1   |   2   |    3   |
     |   |   |   |   |   |    |   |
     |   |   |   |   |   |    |   | f
      \ /     \ /     \ /      \ / 
   (   *       *       *        *   ) (map-indexed f seq-in)

Properties of map

Note
- Mapping over multiple sequences with different lengths will stop at the shortest sequence.
- Map always produces an output sequence that has the same length as the input sequence(s).

Filter

Recall: A predicate is a function that returns true or false.

Here is an example:
```
(defn senior? [age] (>= age 65))
```

General form for filter:

(filter predicate sequence)
;
; predicate is the function
; sequence is the input elements
; returns an output sequence with elements that satisfy the predicate

We can use (filter f seq-in) to generate an output sequence of elements, x, from the input sequence seq-in such that (f x) is true.

  ( o       o       o       o ) seq-in
    |       |       |       |
    |       |       |       | f
    |       |       |       |
   true   false   true    true

  ( o               o       o ) seq-out

Reduce

Reduce is a higher order function that can be used to transform a sequence of elements to a single value.

(reduce f s0 seq-in)

; (f s x) is a function that "updates" state value s by x
; s0: the initial state value
; seq-in: the x's that will be used to update the state.
; returns the final state value.

(reduce f s0 seq-in) accumulates elements in seq-in by incrementally updating some state value, starting with the initial state value of s0.

        ( o      o      o        o ) seq-in
          |      |      |        |
          |f     |f     |f       |f
          |      |      |        |
   s0 --- s1 --- s2 --- s3 --- (reduce f s0 seq-in)
       f      f      f      f

It's possible to omit the initial state: (reduce f seq-in).

This is when the first element is the initial state.

  ( o    o     o      o ) seq-in
     \   |     |      |
      \  |     |      |
       \ |     |      |
        s1 --- s2 --- (reduce f seq-in)