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³ + 2³ + 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:

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.

As examples of the last two:

```
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 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 ...

	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?

		\ 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 word

REVERSE

that 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

reverse

is 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₀, s₁, s₂, ... ), write a word

SUM3 ( seq -- seq )

which produces a new sequence sum3(s) = (s₀ + s₁ + s₂, s₁ + s₂ + s₃, ... )

                : +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*

Generalize

SUM3

SUMN ( seq n -- seq )

, which is able to sum any length window N.

SUMN

should 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 word

ZIP ( 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 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

		: 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 = ; 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:

⁶⁄_1*3 + ⁷⁄_3*7 + ⁸⁄_9*11 + ⁹⁄_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 word

CONSA ( seq seq -- seq )

that

CONS

es 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

Next: Reductions