~
Docs
Courses/Hoon School/16. Functional Programming

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

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.