16. Functional Programming

This module will discuss some gates-that-work-on-gates and other assorted operators that are commonly recognized as functional programming tools.

Given a gate, you can manipulate it to accept a different number of values than its sample formally requires, or otherwise modify its behavior. These techniques mirror some of the common tasks used in other functional programming languages↗ like Haskell, Clojure, and OCaml.

Functional programming, as a paradigm, tends to prefer rather mathematical expressions with explicit modification of function behavior. It works as a formal system of symbolic expressions manipulated according to given rules and properties. FP was derived from the lambda calculus↗, a cousin of combinator calculi like Nock. (See also APL↗.)

Changing Arity

If a gate accepts only two values in its sample, for instance, you can chain together multiple calls automatically using the ;: miccol rune.

> (add 3 (add 4 5))
12

> :(add 3 4 5)
12

> (mul 3 (mul 4 5))
60

> :(mul 3 4 5)
60

This is called changing the arity of the gate. (Does this work on ++mul:rs?)

Binding the Sample

Currying describes taking a function of multiple arguments and reducing it to a set of functions that each take only one argument. Binding, an allied process, is used to set the value of some of those arguments permanently.

If you have a gate which accepts multiple values in the sample, you can fix one of these. To fix the head of the sample (the first argument), use ++cury; to bind the tail, use ++curr.

Consider calculating a x² + b x + c, a situation we earlier resolved using a door. We can resolve the situation differently using currying:

> =full |=([x=@ud a=@ud b=@ud c=@ud] (add (add (mul (mul x x) a) (mul x b)) c))

> (full 5 4 3 2)
117

> =one (curr full [4 3 2])  

> (one 5)  
117

One can also ++cork a gate, or arrange it such that it applies to the result of the next gate. This pairs well with ;: miccol. (There is also ++corl, which composes backwards rather than forwards.) This example decrements a value then converts it to @ux by corking two gates:

> ((cork dec @ux) 20)  
0x13

Exercise: Bind Gate Arguments

• Create a gate ++inc which increments a value in one step, analogous to ++dec.

Exercise: Chain Gate Values

• Write an expression which yields the parent galaxy of a planet's sponsoring star by composing two gates.

Working Across lists

The ++turn function takes a list and a gate, and returns a list of the products of applying each item of the input list to the gate. For example, to add 1 to each item in a list of atoms:

> (turn `(list @)`~[11 22 33 44] |=(a=@ +(a)))
~[12 23 34 45]

Or to double each item in a list of atoms:

> (turn `(list @)`~[11 22 33 44] |=(a=@ (mul 2 a)))
~[22 44 66 88]

++turn is Hoon's version of Haskell's map.

We can rewrite the Caesar cipher program using turn:

|=  [a=@ b=tape]
^-  tape
?:  (gth a 25)
  $(a (sub a 26))
%+  turn  b
|=  c=@tD
?:  &((gte c 'A') (lte c 'Z'))
  =.  c  (add c a)
  ?.  (gth c 'Z')  c
  (sub c 26)
?:  &((gte c 'a') (lte c 'z'))
  =.  c  (add c a)
  ?.  (gth c 'z')  c
  (sub c 26)
c

++roll and ++reel are used to left-fold and right-fold a list, respectively. To fold a list is similar to ++turn, except that instead of yielding a list with the values having had each applied, ++roll and ++reel produce an accumulated value.

> (roll `(list @)`[1 2 3 4 5 ~] add)
q=15

> (reel `(list @)`[1 2 3 4 5 ~] mul)
120

Exercise: Calculate a Factorial

• Use ++reel to produce a gate which calculates the factorial of a number.

Aside on Wet Gates

If you've already encountered wet gates and how they handle their sample, you may eventually circle back around to attempting to write statements which curry a wet gate. For instance, here is an attempt to curry ++reel which itself takes a gate (in this case ++add) as an argument:

> ((curr reel add) `(list @)`[1 2 3 4 ~])
mull-grow
-find.i.a
dojo: hoon expression failed

Unfortunately, ++cury and ++curr don't work with wet gates, and you'll see a mull-grow error.

One solution is to “dry out” the wet gate using ++bake:

> ((curr (bake reel ,[(list @) _add]) add) `(list @)`[1 2 3 4 ~])
10

Classic Operations

Functional programmers frequently rely on three design patterns to produce operations on collections of data:

1. Map. The Map operation describes applying a function to each item of a set or iterable object, resulting in the same final number of items transformed. In Hoon terms, we would say slamming a gate on each member of a list or set. The standard library arms that accomplish this include ++turn for a list, ++run:in for a set, and ++run:by for a map.

2. Reduce. The Reduce operation applies a function as a sequence of pairwise operations to each item, resulting in one summary value. The standard library and ++reel for a list, ++rep:in for a set, and ++rep:by for a map.

3. Filter. The Filter operation applies a true/false function to each member of a collection, resulting in some number of items equal to or fewer than the size of the original set. In Hoon, the library arms that carry this out include ++skim, ++skid, ++murn for a list, and ++rib:by for a map.