# Higher Order Functions

In Smojo, higher-order functions refer specifically to words that enable implicit loops.

To understand what higher order functions are and how are they useful, consider the following three words:

1. `NATURAL-SUM`
computes the sum of natural numbers (i.e. 1 + 2 + 3 + ...)
2. `CUBE-SUM`
computes the sum of the cubes of natural numbers (i.e. 13 + 23 + 33 + ... )
3. `HARMONIC-SUM`
computes the sum of the reciprocals of natural numbers (i.e. 1 ⁄ 1 + 1 ⁄ 2 + 1 ⁄ 3 + ... )

We observe that these three words share a couple of common patterns:

• They sum the terms in a sequence.
• The last two words form this sequence by transforming the natural numbers (1,2,3,...) through the consistent application of a word (i.e.,
`[: dup dup * * ;]`
for
`CUBE-SUM`
and
`[: 1 swap /. ;]`
for
`HARMONIC-SUM`
)

Seen this way, we would then prefer to have:

• a word which expresses the concept of summation of a sequence (instead of having to repeat summation loops three times).
• a word that expresses the concept of transforming a sequence into a new one (again, instead of having to repeat the transformation in a loop.)
Words which accomplish these looping tasks are known in Smojo as "higher order functions", or HOFs for short. The value in this approach is that we can then compose these HOFs to create new and perhaps complex loops easily.

To see this combination capability clearly, imagine we had words
`SUM ( seq -- n )`
to sum a sequence and
`MAP ( seq xt -- seq )`
that transforms a given sequence by applying the XT to each member of the sequence. We can then easily write
`NATURAL-SUM`
,
`CUBE-SUM`
and
`HARMONIC-SUM`
this way:
```		: NATURAL-SUM ( -- n )
1 2 ... SUM ;

: CUBE-SUM ( -- n )
1 2 ... [: dup dup * * ;] MAP SUM ;

: HARMONIC-SUM ( -- n )
1 2 ... [: 1 swap /. ;] MAP SUM ;
```
Here you can see the output of
`MAP`
being fed into the input of
`SUM`
to compute an answer. This idea of composing new loops from two or more old ones is the key idea behind Smojo's higher order functions.

Can we go further?

Consider the word
`NATURAL-PRODUCT`
that gives the product of natural numbers: (i.e., 1 * 2 * 3 ... ). Clearly there is a common pattern with
`NATURAL-SUM`
: you get the one from the other by simply replacing
`+`
with
`*`
. To solve this problem, we could imagine a word
`REDUCE ( seq xt -- * )`
that simply captures the idea of looping alone. The output of
`REDUCE`
depends purely on the action of the XT. We could then write
`NATURAL-SUM`
and
`NATURAL-PRODUCT`
this way:
```			: SUM ( seq -- n )
0 SWAP
['] + REDUCE ;

: NATURAL-SUM ( -- n )
1 2 ... SUM ;

: PRODUCT ( seq -- n )
1 SWAP
['] * REDUCE ;

: NATURAL-PRODUCT ( -- n )
1 2 ... PRODUCT ;
```
Superficially,
`REDUCE ( seq xt -- * )`
may seem like
`MAP ( seq xt -- seq )`
, but there are huge differences:
• `MAP`
commits to produce a sequence as output, while
`REDUCE`
does not.
• `REDUCE`
captures the idea of looping, while
`MAP`
captures the idea of transformation.

Quick Quiz: based on what you have learnt in this section, write a word
`.LIST ( seq -- )`
that prints out all the elements of a sequence.

## Composability

The idea of composibility is an important design principle in Smojo: when writing your Smojo programs, always choose designs that preserve or enhance composibility of words.

As an example, consider the following re-design of our first example:

```			: CUBES ( -- seq )
1 2 ... [: dup dup * * ;] MAP ;

: CUBE-SUM ( -- n )
CUBES SUM ;

: RECIPROCALS ( -- seq )
1 2 ... [: 1 swap /. ;] MAP ;

: HARMONIC-SUM ( -- n )
RECIPROCALS SUM ;
```
This is a poor design choice because none of these words are composable. This alternative is much better:
```			: CUBED ( seq -- seq )
[: dup dup * * ;] MAP ;

: CUBE-SUM ( -- n )
1 2 ... CUBED SUM ;

: INVERTED ( seq -- seq )
[: 1 swap /. ;] MAP ;

: HARMONIC-SUM ( -- n )
1 2 ... INVERTED SUM ;
```
The words
`CUBED ( seq -- seq )`
and
`INVERTED ( seq -- seq )`
are composable, either with themselves or with each other. This offers us the immediate possibility of creating new sums using these words:
```
: X^9-SUM ( -- n )
1 2 ... CUBED CUBED SUM ;

: 1/X^3-SUM ( -- n )
1 2 ... INVERTED CUBED SUM ;
```
Well-designed programs have this idea of composibility on multiple levels. Refining the example above:
```
: CUBE ( n -- n )
dup dup * * ;

: CUBED ( seq -- seq )
['] CUBE MAP ;

: CUBE-SUM ( -- n )
1 2 ... CUBED SUM ;

: RECIPROCAL ( n -- n )
1 swap /. ;

: INVERTED ( seq -- seq )
['] RECIPROCAL MAP ;

: HARMONIC-SUM ( -- n )
1 2 ... INVERTED SUM ;
```
In this design, we have additional words
`CUBE ( n -- n )`
and
`RECIPROCAL ( n -- n )`
that are composable too. This helps us:
1. during testing, by giving us a "toolbox" of words to experiment with through composition,
2. design "one-off" combination words that might not be used again,
3. build new functionality using words across multiple levels,
4. optimize for speed by selecting more efficient combinations.
As examples of the last two:
1. `CUBED :> RECIPROCAL 0.0000001 > ; TAKE-WHILE`
will return a finite subsequence of cubes whose reciprocal is greater than 10-7.
2. `[: CUBE CUBE ;] MAP`
is more efficient than
`CUBED CUBED`
, but less clear.

## Laziness

Higher order functions are very useful as they are able to transform, consolidate or combine sequences.
With the exception of
`REDUCE`
, these functions are lazy in Smojo, which means they only perform their task when an answer is needed.

This property is useful especially in data processing or whenever we need to handle infinite lists.
Once an actual value is needed and read using words like
`HEAD`
, or indirectly with
`REDUCE`
is the sequence evaluated, and even then only until the desired element is reached. Laziness therefore reduces both the running time and amount of memory space needed by your program by avoiding making calculations before they are actually used.

Below are Smojo's primary higher order functions. All are Lazy except
`REDUCE`
.

Word Action
`MAP ( seq xt -- seq )`
Takes a sequence and an XT as arguments. The XT must be a single-valued function. The resulting sequence is a sequence with elements being the output of the function on the elements in the original sequence.
`FILTER ( seq xt -- seq )`
Takes a sequence and an XT as arguments. The XT must be a boolean function. The resulting sequence is a sub-sequence of the original with elements such that the output of the function is true.
`REDUCE ( seq xt -- * )`
Takes a finite sequence and an XT as arguments, and reduces the sequence to a single value. It is not lazy.
`ZIPWITH ( seq seq xt -- seq )`
Takes two sequences and an XT as arguments. The XT is used to combine the sequences element-wise, resulting with a third sequence.
`TAKE-WHILE ( seq xt -- seq )`
Creates a sub-sequence by selecting elements as long as the XT is true. It stops taking elements when the XT returns false. For example:
`1 2 ... :> 5 < ; TAKE-WHILE`
returns the sequence (1,2,3,4).

## Examples

Example 1: Find all squares

```	: ^2 dup * ;

1 2 ... ' ^2 map .list
1 4 9 16 25 ...
```
or
```	1 2 ... :> dup * ; map .list
1 4 9 16 25 ...
```
Example 2: Find all even numbers
```	: even? 2 mod 0 = ;

1 2 ... ' even? filter .list
2 4 6 8 10 ...
```
Example 3: Find the numbers divisible by 5
```	: div? ( n -- xt )
{ n } [: n mod 0 = ;] ;

1 2 ... 5 div? filter .list
5 10 15 20 25 30 ...
```
Example 4: Find the maximum number
```	0 1 2 ... 100 take ' max reduce .
100.0 ok
```
Remember that unlike
`MAP`
,
`FILTER`
and
`ZIPWITH`
,
`REDUCE`
is not lazy.
`REDUCE`
will try to iterate over the entire sequence, so you must ensure it is finite before attempting a reduction. In this example, the word
`MAX`
needs two arguments. Note that 0, which acts as the first argument is already on the stack and is constantly updated by
`MAX`
during reduction. The second argument is obtained from the sequence as
`REDUCE`
iterates through it.

Example 5: Find the sequence resulting from the element-wise summation between the two sequences

```	1 2 ...
100 99 ...
' + zipwith .list
101 101 101 101 ...
```
Example 6: Find all squares divisible by 17 and 23
``` 	1 2 ... ' ^2 map 17 div? filter 23 div? filter .list
152881 611524 1375929 2446096 3822025 ...
```

## Quiz

### Question 1

Write a word
`MINIMUM ( seq -- n )`
to find the minimum value of a sequence. Does your word make any assumptions about the maximum value?

### Question 2

Write a word
`REVERSE`
that reverses any finite sequence. Can this word be Lazy? Is it possible to reverse infinite sequences?

### Question 3*

Given a sequence s = (s0, s1, s2, ... ), write a word
`SUM3 ( seq -- seq )`
which produces a new sequence sum3(s) = (s0 + s1 + s2, s1 + s2 + s3, ... )

### Question 4*

Generalize
`SUM3`
to
`SUMN ( seq n -- seq )`
, which is able to sum any length window N.
`SUMN`
should take the initial sequence and N as input.

### Question 5*

Write a word
`ZIP ( seq seq -- seq )`
that produces 2-tuples from each pair of elements of the input sequences.

### Question 6*

Write a word
`TAKE ( seq n -- seq )`
that produces a sequence of the first N elements of an infinite sequence. Hint: You may have to use
`ZIPWITH`
and
`TAKE-WHILE`
.

### Question 7

Is:

```1 2 ...
255 TAKE
:> 31 MOD 0 = ; FILTER```
the same as
```1 2 ...
:> 31 MOD 0 = ; FILTER
255 TAKE ```
? Explain why.

### Question 8*

Write a word that performs this sum over N terms:

61*3 + 73*7 + 89*11 + 927*15 + ...

### Question 9

Write a word
`CONSA ( seq seq -- seq )`
that
`CONS`
es the second (finite) list to the first.