# 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:

NATURAL-SUM

computes the sum of natural numbers (i.e. 1 + 2 + 3 + ...)CUBE-SUM

computes the sum of the cubes of natural numbers (i.e. 1^{3}+ 2^{3}+ 3^{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 * * ;]

forCUBE-SUM

and[: 1 swap /. ;]

forHARMONIC-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.)

**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-SUMand

HARMONIC-SUMthis 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

MAPbeing fed into the input of

SUMto 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 wordNATURAL-PRODUCTthat 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

REDUCEdepends purely on the action of the XT. We could then write

NATURAL-SUMand

NATURAL-PRODUCTthis 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, whileREDUCE

does not.REDUCE

captures the idea of**looping**, whileMAP

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:

- during testing, by giving us a "toolbox" of words to experiment with through composition,
- design "one-off" combination words that might not be used again,
- build new functionality using words across multiple levels,
- optimize for speed by selecting more efficient combinations.

CUBED :> RECIPROCAL 0.0000001 > ; TAKE-WHILE

will return a finite subsequence of cubes whose reciprocal is greater than 10^{-7}.[: CUBE CUBE ;] MAP

is more efficient thanCUBED CUBED

, but less clear.

## Laziness

Higher order functions are very useful as they are able to transform, consolidate or combine sequences. With the exception ofREDUCE, 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

REDUCEis 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-WHILEreturns 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 okRemember that unlike

MAP,

FILTERand

ZIPWITH,

REDUCEis not lazy.

REDUCEwill try to iterate over the entire sequence, so you

__must ensure it is finite before attempting a reduction.__In this example, the word

MAXneeds two arguments. Note that 0, which acts as the first argument is already on the stack and is constantly updated by

MAXduring reduction. The second argument is obtained from the sequence as

REDUCEiterates 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 wordMINIMUM ( seq -- n )to find the minimum value of a sequence. Does your word make any assumptions about the maximum value?

\ assume there is at least one item in seq : minimum ( seq -- n ) dup head swap tail ['] min reduce ; 1 2 ... 10 take minimum . \ 1 10 9 ... 10 take minimum . \ 1 1 2 ... :> 1 swap /. ; map 10 take minimum . \ 0.1

### Question 2

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

: reverse ( seq -- seq ) nil swap ['] cons reduce ; 1 2 ... 10 take reverse dup . cr \ ( 10 ( 9 ( ... ) ) ) .list \ 10 9 8 7 6 5 4 3 2 1

reverseis not possible to be lazy. The whole sequence has to be known so reversing an infinite sequence are not possible.

### Question 3*

Given a sequence s = (s_{0}, s

_{1}, s

_{2}, ... ), write a word

SUM3 ( seq -- seq )which produces a new sequence sum3(s) = (s

_{0}+ s

_{1}+ s

_{2}, s

_{1}+ s

_{2}+ s

_{3}, ... )

: +s ( seq seq -- seq ) ['] + zipwith ; : sum3 ( seq -- ) \ (s0, s1, s2, ...) (s1, s2, s3, ...) (s2, s3, s4, ...) dup tail dup tail +s +s ; 1 2 ... sum3 10 take .list \ 6 9 12 ... 1 3 ... sum3 10 take .list \ 9 15 21 ...

### Question 4*

GeneralizeSUM3to

SUMN ( seq n -- seq ), which is able to sum any length window N.

SUMNshould take the initial sequence and N as input.

: +s ( seq seq -- seq ) ['] + zipwith ; / TIMES ( n xt -- ) runs the xt , n times. : SUMN ( seq n -- seq ) 1- { n } n [: dup tail ;] times n ['] +s times ; 1 2 ... 2 sumN 5 take .list \ 3 5 7 9 11 1 2 ... 3 sumN 5 take .list \ 6 9 12 15 18 1 2 ... 4 sumN 5 take .list \ 10 14 18 22 26

### Question 5*

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

: pair ( a b -- a,b ) 2 tuple ; : zip ( seq seq -- seq ) ['] pair zipWith ; 1 2 ... 3 take 3 5 ... 3 take zip dup .list \ 3 tuple objects dup head .tuple \ (1,3) dup tail head .tuple \ (2,5) dup tail tail head .tuple \ (3,7)

### Question 6*

Write a wordTAKE ( seq n -- seq )that produces a sequence of the first N elements of an infinite sequence. Hint: You may have to use

ZIPWITHand

TAKE-WHILE.

: take ( seq n -- seq ) { n } 0 1 ... [: n < ;] take-while ['] drop zipwith ; 1 2 ... 5 take .list \ 1 2 3 4 5 2 4 ... 4 take .list \ 2 4 6 8 1 1 ... 3 take .list \ 1 1 1 3 1 ... 2 take .list \ 3 1 2 9 ... 1 take .list \ 2

### Question 7

Is:

1 2 ... 255 TAKE :> 31 MOD 0 = ; FILTERthe same as

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

### Question 8*

Write a word that performs this sum over N terms:

^{6}⁄

_{1*3}+

^{7}⁄

_{3*7}+

^{8}⁄

_{9*11}+

^{9}⁄

_{27*15}+ ...

: sum ( seq -- n ) 0 swap ['] +. reduce ; : *s ( seq seq -- seq ) ['] *. zipwith ; : \s ( seq seq -- seq ) ['] /. zipwith ; : series ( n -- n ) { n } 6 7 ... \ 6 7 8 9 ... 0 1 ... [: 3 swap ^ ;] map \ 1 3 9 27 ... 0 1 ... [: 4 * 3 + ;] map \ 3 7 11 15 ... *s \s n take sum ; 0 series . cr \ 0 1 series . cr \ 2.0 2 series . cr \ 2.33333333 3 series . cr \ 2.41414141 4 series . cr \ 2.43636363 5 series . cr \ 2.44286136

### Question 9

Write a wordCONSA ( seq seq -- seq )that

CONSes the second (finite) list to the first.

: CONSA ( seq seq -- seq ) reverse ['] cons reduce ; 1 2 ... 3 take 10 9 ... 5 take consa dup .list \ 10 9 8 7 6 1 2 3