# Basics Module `FuPy.basics` provides the basic definitions for functional programming in Python. In particular, it defines elementary types and type constructors, and elementary functions and function constructors. ## Contents * [Predefined types](#predefined-types) * [Predefined `Func`-wrapped functions](#predefined-func-wrapped-functions) * [Function combinators](#function-combinators) * [Lambda expressions](#lambda-expressions) * [Operator sections](#operator-sections) * [Printing of `Func` values](#printing-of-func-values) * [Examples](#examples) ## Predefined types There are five predefined types in `FuPy.basics`: * **`Empty`**, a type without any values. This type exists mostly for theoretical purposes. Note that `Func[Empty, Empty]` has one value, viz. the "empty" function (which is useless, because it cannot be applied to any value). Also see the predefined function `undefined` with type `Func[A, Empty]`. * **`Unit`**, a type with only one value, viz. `unit` Value `unit` is equivalent to the empty tuple `()`, in the sense that calling a `Func`-wrapped function `f` as `f(unit)` and `f()` amount to the same thing. Such a function is basically a constant (since functions should not have side effects). Also see the predefined function `const`. * **`Either[A, B] = Left[A] | Right[B]`**, a _(disjoint) sum type_, consisting of _left-injected_ `A`-values and _right_injected_ `B`-values. Also see the two _injection_ functions `left` and `right` below, and the _case_ function combinator `|`. * **`Both[A, B] = tuple[A, B]`**, a _(Cartesian) product type_, consisting of tuples with a left component from `A` and a right component from `B`. Since it is just a type alias for `tuple[A, B]`, tuple values can be written as usual: `(a, b)`. We introduced the name `Both` to emphasize the _duality_ with `Either`. Also see the _projection_ functions `first` and `second` below, and the _split_ function combinator `&`. * **`Func[A, B]`**, a _function type_, consisting of functions from `A` to `B`. Keep in mind that these functions take exactly 1 argument. However, for convenience, they can be called with zero or more than one argument. Moreover, one can wrap functions with zero or more than one argument in `Func`. To make this work, `FuPy` applies auto (un)packing of arguments. - If `f` is defined with `r` required parameters (`r != 1`), then the call `Func(f)(a) = f(*a)`, that is, argument `a` is expected to be an `r`-_tuple_, and it is automatically _unpacked_ to provide arguments to `f`. In particular, `Func(f)(()) = Func(f)(unit) = f()` and `Func(f)((a, b, ...)) = f(a, b, ...)`. - If `f` is defined with `r` required parameters (`r == 1`), then the call `Func(f)(*a) = f(a)` (i.e., `Func(f)()` or `Func(f)(a, b, ...)`), that is, argument `*a` is expected to consist of `r` values, and these are automatically _packed_ to provide an `r`-tuple as arguments to `f`. In particular, `Func(f)() = Func(f)(unit) = f(()) = f(unit)` and `Func(f)((a, b, ...)) = f(a, b, ...)`. The types `Either`, `Both`, and `Func` are _polymorphic_ (taking type parameters) and these can be used to define more complex types. When using only types `Empty`, `Unit`, `Both`, and `Either`, the resulting type is known as a _polynomial type_, and it has a _finite_ number of values. For instance, `bool` is isomorphic to `Either[Unit, Unit]`, where `True ~ left(unit)` and `False ~ right(unit)`. Note that these `FuPy` types can also be used with Python types. `FuPy.laziness` adds lazy expressions (to suspend computations). `FuPy.fixpoints` adds the ability to define _infinite_ types (both with an infinite number of values and (lazy) values that are infinite), as _fixpoints_ of _functors_, where such functors are constructed using `Unit`, `Either`, `Both` (i.e., polynomial), and other fixpoint types. It also adds factories for functions to/from such types. `FuPy.prelude` adds some standard infinite types, such as _natural numbers_ and (possibly infinite) _lists_, and related functions. ## Predefined `Func`-wrapped functions `FuPy.basics` defines the following `Func`-wrapped functions: * **`undefined[A]: Func[A, Empty]`** (raises a `ValueError`; prints as '⊥') * **`id_[A}: Func[A, A]`** (polymorphic identity function: `id_(x) = x; prints as 'id') * **`const[A, B]: Func[B, Func[A, B]]`** (polymorphic constant function constructor: `const(b)(a) = b`; `const(b)` is said to be a _constant function_, in that it ignores its argument `a` and always returns `b`; `const` prints as '(°)' and `const(b)` as 'b°'; often we use type `Unit` for `A`; we use the degree symbol '°' because Unicode lacks of a superscript bullet, which is our preferred Math notation for constant functions) * **`eq_[A]: Func[Both[A, A], bool]`** (uncurried polymorphic equality test: `eq_(a, b) = (a == b)`; prints as '=') * **`left[A, B]: Func[A, Either[A, B]]`** (_injection_ of value into left component of `Either` type: `left(v) = Left(value=v)`; prints as '↪︎', also pronounced as "inject from the left") * **`right[A, B]: Func[B, Either[A, B]]`** (_injection_ of value into right component of `Either` type: `right(v) = Right(value=v)`; prints as '↩', also pronounced as "inject from the right") * **`guard[A]: Func[Func[A, bool], Func[A, Either[A, A]]`** (conditional injection based on predicate: `guard(p)(a) = left(a) if p(a) else right(a)`; `guard` prints as '(?)' and `guard(p)` as 'p?') * **`first[A, B]: Func[Both[A, B], A]`** (_projection_ of tuple on first component: `first(a, b) = a`; prints as '≪', also pronounced as "project to the left") * **`second[A, B]: Func[Both[A, B], B]`** (_projection_ of tuple on second component: `second(a, b) = b`; prints as '≫', also pronounced as "project to the right") * **`curry[A, B, C]: Func[Func[Both[A, B], C], Func[A, Func[B, C]]`** (make a _curried_ function from an uncurried function: `curry(f)(a)(b) = f(a, b)`) * **`uncurry[A, B, C]: Func[A, Func[B, C]], Func[Both[A, B], C]]`** (make an _uncurried_ function from a curried function: `uncurry(f)(a, b) = f(a)(b)`) * **`flip[A, B, C]: Func[Func[A, Func[B, C]], Func[B, Func[A, C]]]`** (_flip_ arguments of a curried function: `flip(f)(a)(b) = f(b)(a)`) * **`ap[A, B]: Func[Both[Func[A, B], A], B]`** (_apply_ function to argument: `ap(f, a) = f(a)` ## Function combinators There is special group of predefined (polymorphic, uncurried, _higher-order_) functions. They are said to be higher-order functions because they take arguments of type `Func` and return results of type `Func`. These are known as _function combinators_. * **`compose[A, B, C]: Func[Both[Func[B, C], Func[A, B]], Func[A, C]]`** (_compose_ two functions head-to-tail: `compose(f, g)(a) = f(g(a()))`) * **`split[A, B, C]: Func[Both[Func[A, C], Func[A, B]], Func[A, Both[B, C]]`** (_split_ argument to both functions: `split(f, g)(a) = (f(a), g(a))`; prints as '△') * **`case_[A, B, C]: Func[Both[Func[A, C], Func[B, C]], Func[Either[A, B], C]`** (_case distinction_ on argument to choose between two functions: `case_(f, g)(left(a) = f(a)` and `case_(f, g)(right(b)) = g(b))`; prints as '▽') * **`ftimes[A, B, C, D]: Func[Both[Func[A, C], Func[B, D]], Func[Both[A, B], Both[C, D]]`** (_functorial product_: `ftimes(f, g)(a, b) = (f(a), g(b))`; we have the equality: `ftimes(f, g) == split(co(f, first), co(g, second))`; prints as '⨯') * **`fplus[A, B, C, D]: Func[Both[Func[A, C], Func[B, D]], Func[Either[A, B], Either[C, D]]`** (_functorial sum_: `fplus(f, g)(left(a)) = left(f(a))` and `fplus(f, g)(right(b)) = right(g(b))`; we have the equality: `fplus(f, g) == case_(co(left, f), co(right, g))`; prints as '+') * **`fpower[A]: Func[Both[Func[A, A], int], Func[A, A]]`** (_iterated_ function application, repeated function composition: `(f ** 0)(x) = x`, `(f ** n)(x) = (f ** (n-1))(f(x)) = f(f ** (n-1)(x))`; prints as '**') * **`fpower_left[A]: Func[Both[Func[A, A], int], Func[A, A]]`** (_iterated_ function application, repeated function composition, _associating to the left_: `fpower_left(f, 0)(x) = x`, `fpower_left(f, n)(x) = fpower_left(f, n - 1)(f(x))`; N.B. `fpower(f, n) = fpower_left(f, n)`, but they differ in the order of association, which may affect performance (especially in the light of laziness): - `fpower(f, n) = f ⚬ (f ⚬ f)` - `fpower_left(f, n) = (f ⚬ f) ⚬ f` All the function combinators also have corresponding infix operators: | operator | function | `__dunder__` | prints as | |:--------:|:---------:|:---------------------------:|:---------:| | `@` | `compose` | `__matmul__`, `__rmatmul__` | ⚬ | | `&` | `split` | `__and__`, `__rand__` | △ | | `\|` | `case_` | `__or__`, `__ror__` | ▽ | | `*` | `ftimes` | `__mul__`, `__rmul__` | ⨯ | | `+` | `fplus` | `__add__`, `__radd__` | + | | `**` | `fpower` | `__pow__`, `__rpow__` | ** | For these function combinators to be recognized, at least one of the functions involved must have been wrapped in `Func`. The other function (if applicable) could be a plain function, which will then automatically be wrapped in `Func`. ### Operator precedence It is important to keep in mind that Python's rules for operator precedence differ from those rules for Math notation. The following table shows the operator precedence order for Python (from higher to lower) | Python | |:------:| | ** | | @, * | | + | | & | | \| | Furthermore, in Python operators on the same precedence level associate to the left, except for `**` which associates to the right. The following table shows the operator precedence order for Math notation (from higher to lower). | Math | |:----:| | ^ | | ⚬ | | △, ⨯ | | ▽, + | Furthermore, in Math notation, operators on the same level, except for ⚬, must be explicitly parenthesized. Note that in Math notation only ⚬ is _associative_. The following situations may be counterintuitive: | Python | prints Math | meaning | |:-------------:|:-----------:|:-----------:| | `f * g @ h` | (f ⨯ g) ⚬ h | | | `f * (g @ h)` | f ⨯ g ⚬ h | f ⨯ (g ⚬ h) | | `f + g & h` | (f + g) △ h | | | `f + (g & h)` | f + g △ h | f + (g △ h) | You can set `Func.fully_parenthesized = True` to make expressions print in a fully parenthesized format. ## Lambda expressions In Python, one can use _lambda expressions_ of the form: `lambda` _parameters_`:` _expression_ where _parameters_ is a comma-separated list of names. Names that occur in _expression_ and that are not among the _parameters_ are called _free variables_. If a free variable appears in the _local_ namespace where the lambda expression is being defined, then it is bound to the value for that name from the local namespace. This is known as _early binding_. The resulting binding is incorporated in the code object compiled from the lambda expression (these early bindings are known as a _closure_). When a lambda expression is called with arguments, the early bound names are taken from the closure produced at compile time. If a free variable doesn't appear in the local namespace, then it is left unbound at compile time. However, a reference to the global namespace is bound to the code object at compile time. When a lambda expression is called with arguments, the unbound (global) names are taken from the global namespace bound to the code object. This is called _late binding_. Keep in mind that the bindings of names-to-values in this global namespace could have mutated since the lambda expression was compiled. `FuPY` provides a way of defining `Func`-wrapped lambda abstractions of the form (note that the argument to `la` is a _string_) `la('`_parameters_`:` _expression_`')` where _parameters_ is a comma-separated list of parameters, in which each parameter is either - a single name (like with regular Python lambda expressions) - an empty place, or - a tuple of names (separated by commas); this tuple can be empty: `()` The resulting `Func`-wrapped function is _curried_ on the first level of parameters and _uncurried_ on parameters of a _tuple pattern_: * For `f = la('a, b: (b, a)')`, we have `f(a)(b) = (b, a)`. * For `f = la('(a, b): (b, a)')`, we have `f(a, b) = (b, a)`. * For `f = la('a, (b, c): ((a, b), c)`, we have `f(a)(b, c) = ((a, b), c)` That is, functionally we have * `la('a, b: (b, a)') = Func(lambda a: Func(lambda b: (b, a))` * `la('(a, b): (b, a)) = Func(lambda a, b: (b, a))` where each `Func`tion is printable. ## Operator sections `FuPy.basics` defines the dummy argument `x_` to behave in a special way when appearing as argument of many Python operators, such as `+`, `-`, `*`, etc. to mimic _operator sectioning_ (as e.g. known in Haskell). > Unless you have a special use for `_` (for example when running an interactive Python interpreter, such as iPython, e.g. in a Jupyter notebook), it is recommended to define `_ = x_` after importing `FuPy`. The examples below assume this definition is in effect. In general, let _op_ be a binary operator and `a` a value of an appropriate type. Then the following expressions can be used: * `_` _op_ `a`, better written as `(_` _op_ `a)`), means `la('x: x` _op_ `a')`. * `a` _op_ `_`, better written as `(a` _op_ `_)`), means `la('x: a` _op_ `x')`. * `_` _op_ `_`, better written as `(_` _op_ `_)`), means `la('x, y: x` _op_ `y')`. Note that this is a _curried_ function. Currently, the following operators are supported: | operator | `__dunder__` | prints as | |:--------:|:--------------------------------:|:---------:| | `==` | `__eq__` | = | | `!=` | `__ne__` | != | | `>=` | `__ge__` | ≥ | | `>` | `__gt__` | > | | `<=` | `__le__` | ≤ | | `<` | `__lt__` | < | | `+` | `__add__`, `__radd__` | + | | `-` | `__sub__`, `__rsub__` | - | | `*` | `__mul__`, `__rmul__` | *, ⨯ | | `@` | `__matmul__`, `__matmul__` | ⚬ | | `/` | `__truediv__`, `__rtruediv__` | / | | `//` | `__floordiv__`, `__rfloordiv__` | div | | `%` | `__mod__`, `__rmod__` | mod | | `**` | `__pow__`, `__rpow__` | ** | | `&` | `__and__`, `__rand__` | △, & | | `\|` | `__or__`, `__ror__` | ▽, \| | | `divmod` | `__divmod__`, `__rdivmod__` | divmod | ## Printing of `Func` values `Func` wrapped functions, including those constructed by `la`, can be nicely printed. This makes it easier to inspect the results of higher-order functions. Currently, only printing in so-called _Math notation_ is supported. In the future, we may support printing in Python, Haskell, and LaTeX. Note however that `Func`tions created via `la` (lambda abstraction) print in a mixed notation: `la('params: expr')` prints as ```λ params: `expr````. That is, the body expression `expr` is shown between backquotes to emphasize that it uses Python notation. ## Examples The following examples require ```python from FuPy.basics import * from operator import add, mul _ = x_ ``` Also see [demo.py](../examples/demo.py). ### Operator sections and lambda abstraction Let's define some simple functions using operator sections and a lambda abstraction: ```python inc = (_ + 1) # increment by one dbl = (2 * _) # double sqr = la('x: x * x') # square ``` ### Function combinators ```python print(f"({inc @ dbl}).3 = {(inc @ dbl)(3)}") print(f"({inc | dbl}).(↪︎.3) = {(inc | dbl)(left(3))}") print(f"({inc | dbl}).(↩︎.3) = {(inc | dbl)(right(3))}") print(f"({inc & dbl}).3 = {(inc & dbl)(3)}") print(f"({inc + dbl}).(↪︎.3) = {(inc + dbl)(left(3))}") print(f"({inc + dbl}).(↩︎.3) = {(inc + dbl)(right(3))}") print(f"({inc * dbl}).(1, 3) = {(inc * dbl)(1, 3)}") print(f"({sqr ** 3}).2 = {(sqr ** 3)(2)}") ``` produces as output (in some cases, `force` is needed) ``` ((+1) ⚬ (2*)).3 = 7 ((+1) ▽ (2*)).(↪︎.3) = 4 ((+1) ▽ (2*)).(↩︎.3) = 6 ((+1) △ (2*)).3 = (4, 6) ((+1) + (2*)).(↪︎.3) = ↪︎.4 ((+1) + (2*)).(↩︎.3) = ↩︎.6 ((+1) ⨯ (2*)).(1, 3) = (2, 6) ((λ x: `x * x`)^3).2 = 256 ``` The duality between ▽ and △ becomes even clearer with ```python print(f"≪.(({inc & dbl}).3) = {first((inc & dbl)(3))}") print(f"≫.(({inc & dbl}).3) = {second((inc & dbl)(3))}") ``` which produces as output ``` ≪.(((+1) △ (2*)).3) = 4 ≫.(((+1) △ (2*)).3) = 6 ``` Note that we have the algebraic equalities: ``` (f ▽ g) ⚬ ↪︎ = f = ≪ ⚬ (f △ g) (f ▽ g) ⚬ ↩︎ = f = ≫ ⚬ (f △ g) ``` ### Factorial In functional programming, the factorial function serves as _Hello World_ example. A typical _imperative_ definition of this function in Python is ```python def factorial(n: int) -> int: """Iterative factorial function: factorial(n) = n!. """ result = 1 for i in range(1, n + 1): result *= i return result ``` Pure functional programming has no loops. Instead, one needs to use recursion. Here is a recursive definition of the factorial function: ```python def fac(n: int) -> int: """Recursive factorial function: fac(n) = n!. """ return 1 if n == 0 else n * fac(n - 1) ``` To make the calls of `fac` traceable, wrap its definition in `Func` via the decorator `func`. It is also illustrative to trace the multiplications. This can be done by using the standard operator `mul` and wrapping it in `Func`. ```python @func def fac(n: int) -> int: """Recursive factorial function: fac(n) = n!. """ return 1 if n == 0 else op.mul(n, fac(n - 1)) ``` The evaluation of `fac(3)` can be traced by ```python trace(lambda: fac(3), live=True) ``` which results in the following output, using Math notation: ``` 0 Apply: ┌ fac.3 1 Motivate: = { def. of fac } 2 Apply: │ ┌ fac.2 3 Motivate: │ = { def. of fac } 4 Apply: │ │ ┌ fac.1 5 Motivate: │ │ = { def. of fac } 6 Apply: │ │ │ ┌ fac.0 7 Motivate: │ │ │ = { def. of fac } 8 Return: │ │ │ └ 1 9 Apply: │ │ │ ┌ mul.(1, 1) 10 Motivate: │ │ │ = { def. of mul } 11 Return: │ │ │ └ 1 12 Return: │ │ └ 1 13 Apply: │ │ ┌ mul.(2, 1) 14 Motivate: │ │ = { def. of mul } 15 Return: │ │ └ 2 16 Return: │ └ 2 17 Apply: │ ┌ mul.(3, 2) 18 Motivate: │ = { def. of mul } 19 Return: │ └ 6 20 Return: └ 6 ``` ### Factorial with function combinators Let's rewrite the body of `fac` in terms of function combinators, such that we get an expression where a function is applied to `n`: ``` 1 if n == 0 else n * fac(n - 1) = { operator mul } 1 if n == 0 else mul(n, fac(n - 1)) = { identity function, operator section, composition } 1 if n == 0 else mul(id_(n), (fac @ (_ - 1))(n)) = { split } 1 if n == 0 else mul((id_ & (fac @ (_ - 1)))(n)) = { constant function, composition } const(1)(n) if n == 0 else (mul @ (id_ & (fac @ (_ - 1))))(n) = { guard, case } ((const(1) | mul @ (id_ & (fac @ (_ - 1)))) @ guard(_ == 0))(n) ``` Let's define ```python pre_fac = la('x: (const(1) | mul @ (id_ & (x @ (_ - 1)))) @ guard(_ == 0)').define_as("pre_fac") ``` Then apparently `fac` satisfies the equation ```python fac = pre_fac(fac) ``` In Math notation, the right-hand side prints as ``` (1° ▽ mul* ⚬ (id △ fac ⚬ (-1))) ⚬ (=0)? ``` Note that `mul*` indicates that the tuple produced by the split combinator △ is unpacked when `mul` is applied. Also see `pre_fac` in the [example for `fix`](fixpoints.md#example-of-using-fix-factorial-again). Here is a trace of `pre_fac(const(2))(3)` (some details have been suppressed): ``` 3 Apply: ┌ pre_fac.(2°) 4 Motivate: = { def. of pre_fac } 5 Apply: │ ┌ (λ x: `(const(1) | mul @ (id_ & x @ (_ - 1))) @ guard(_ == 0)`).(2°) 6 Motivate: │ = { def. of λ } 20 Return: │ └ (1° ▽ mul* ⚬ (id △ 2° ⚬ (-1))) ⚬ (=0)? 21 Return: └ (1° ▽ mul* ⚬ (id △ 2° ⚬ (-1))) ⚬ (=0)? 22 Apply: ┌ ((1° ▽ mul* ⚬ (id △ 2° ⚬ (-1))) ⚬ (=0)?).3 23 Motivate: = { def. of ⚬ } 24 Apply: │ ┌ ((=0)?).3 25 Motivate: │ = { def. of ? } 26 Apply: │ │ ┌ (=0).3 27 Motivate: │ │ = { def. of (=0) } 28 Return: │ │ └ False 29 Return: │ └ Right(value=3) 30 Apply: │ ┌ (1° ▽ mul* ⚬ (id △ 2° ⚬ (-1))).Right(value=3) 31 Motivate: │ = { def. of ▽ } 32 Apply: │ │ ┌ (mul* ⚬ (id △ 2° ⚬ (-1))).3 33 Motivate: │ │ = { def. of ⚬ } 34 Apply: │ │ │ ┌ (id △ 2° ⚬ (-1)).3 35 Motivate: │ │ │ = { def. of △ } 36 Apply: │ │ │ │ ┌ id.3 37 Motivate: │ │ │ │ = { def. of id } 38 Return: │ │ │ │ └ 3 39 Apply: │ │ │ │ ┌ (2° ⚬ (-1)).3 40 Motivate: │ │ │ │ = { def. of ⚬ } 41 Apply: │ │ │ │ │ ┌ (-1).3 42 Motivate: │ │ │ │ │ = { def. of (-1) } 43 Return: │ │ │ │ │ └ 2 44 Apply: │ │ │ │ │ ┌ (2°).2 45 Motivate: │ │ │ │ │ = { def. of ° } 46 Return: │ │ │ │ │ └ 2 47 Return: │ │ │ │ └ 2 48 Return: │ │ │ └ (3, 2) 49 Apply: │ │ │ ┌ mul.(3, 2) 50 Motivate: │ │ │ = { def. of mul; auto-unpack arguments from tuple } 51 Return: │ │ │ └ 6 52 Return: │ │ └ 6 53 Return: │ └ 6 54 Return: └ 6 ``` ### Tupled factorial Rather than using an explicit recursion, the factorial function can also be expressed via function exponentiation. To that end, specify the tupled factorial function `tfac` by ```python tfac(n) = (fac(n), n + 1) ``` This can be written _pointfree_ as an equation on functions by using the split combinator and operator sectioning: ```python tfac = fac & (_ + 1) ``` For `tfac` we calculate the base case (using Math notation): ``` tfac.0 = { specification of tfac } (fac.0, 0 + 1) = { def. of fac, arithmetic } (1, 1) ``` And for the step case: ``` tfac.(n + 1) = { specification of tfac } (fac.(n + 1), (n + 1) + 1) = { def. of fac } ((n + 1) * fac.n, (n + 1) + 1) = { introduce let expression } let (frn, n1) = (fac.n, n + 1) in (n1 * frn, n1 + 1) = { tfac.n = (fac.n, n + 1) } let (frn, n1) = tfac.n in (n1 * frn, n1 + 1) = { split, operator sectioning, composition } let (frn, n1) = tfac.n in (mul △ (+1) ⚬ ≫).(frn, n1) = { eliminate let } (mul △ (+1) ⚬ ≫).(tfac.n) ``` Therefore, `tfac.n` can be computed by `n` applications of function `mul △ (+1) ⚬ ≫` to `(1, 1)`. That is, we have ``` tfac.n = ((mul △ (+1) ⚬ ≫)^n).(1, 1) ``` In `FuPy` syntax, we can define ```python @func def tfac(n: int) -> int: """Tupled factorial: tfac(n) = (factorial(n), n + 1). """ return ((mul & ((_ + 1) @ second)) ** n)(1, 1) ``` Tracing of `tfac(3)` shows (suppressing some details): ``` tracing tfac(3): 0 Apply: ┌ tfac.3 1 Motivate: = { def. of tfac } 7 Apply: │ ┌ ((mul △ (+1) ⚬ ≫)^3).(1, 1) 8 Motivate: │ = { def. of ^; auto-pack arguments in tuple } 9 Apply: │ │ ┌ ((mul △ (+1) ⚬ ≫)^2).(1, 1) 10 Motivate: │ │ = { def. of ^ } 11 Apply: │ │ │ ┌ (mul △ (+1) ⚬ ≫).(1, 1) 12 Motivate: │ │ │ = { def. of △ } 13 Apply: │ │ │ │ ┌ mul.(1, 1) 14 Motivate: │ │ │ │ = { def. of mul; auto-unpack arguments from tuple } 15 Return: │ │ │ │ └ 1 16 Apply: │ │ │ │ ┌ ((+1) ⚬ ≫).(1, 1) 17 Motivate: │ │ │ │ = { def. of ⚬ } 18 Apply: │ │ │ │ │ ┌ ≫.(1, 1) 19 Motivate: │ │ │ │ │ = { def. of ≫ } 20 Return: │ │ │ │ │ └ 1 21 Apply: │ │ │ │ │ ┌ (+1).1 22 Motivate: │ │ │ │ │ = { def. of (+1) } 23 Return: │ │ │ │ │ └ 2 24 Return: │ │ │ │ └ 2 25 Return: │ │ │ └ (1, 2) 26 Apply: │ │ │ ┌ (mul △ (+1) ⚬ ≫).(1, 2) 27 Motivate: │ │ │ = { def. of △ } 28 Apply: │ │ │ │ ┌ mul.(1, 2) 29 Motivate: │ │ │ │ = { def. of mul; auto-unpack arguments from tuple } 30 Return: │ │ │ │ └ 2 31 Apply: │ │ │ │ ┌ ((+1) ⚬ ≫).(1, 2) 32 Motivate: │ │ │ │ = { def. of ⚬ } 39 Return: │ │ │ │ └ 3 40 Return: │ │ │ └ (2, 3) 41 Return: │ │ └ (2, 3) 42 Apply: │ │ ┌ (mul △ (+1) ⚬ ≫).(2, 3) 43 Motivate: │ │ = { def. of △ } 44 Apply: │ │ │ ┌ mul.(2, 3) 45 Motivate: │ │ │ = { def. of mul; auto-unpack arguments from tuple } 46 Return: │ │ │ └ 6 47 Apply: │ │ │ ┌ ((+1) ⚬ ≫).(2, 3) 48 Motivate: │ │ │ = { def. of ⚬ } 55 Return: │ │ │ └ 4 56 Return: │ │ └ (6, 4) 57 Return: │ └ (6, 4) 58 Return: └ (6, 4) ``` ### Flipped curried generalized factorial The generalized factorial function `gfac` is specified by `gfac(a, n) = a * fac(n)`. One can calculate the following (tail-recursive) definition: ```python @func def gfac(a: int, n: int) -> int: """Tail recursive curried generalized factorial: gfac(a, n) = a * fac(n). fac(n) = gfac(1, n) """ if n == 0: return a else: return gfac(a * n, n - 1) ``` When `gfac` is curried and then flipped, we get function `gfac_fc = flip @ curry @ gfac`, for which we have `gfac_fc(n)(a) = gfac(a, n)`. On can calculate the following definition for `gfac_fc`: ```python @func def gfac_fc(n: int) -> Func[int, int]: """Flipped curried generalized factorial: gfac_fc(n)(a) = a * fac(n). fac(n) = gfac_fc(n)(1) """ return id_ if n == 0 else gfac_fc(n - 1) @ (_ * n) ``` What does the function returned by `gfac_fc(5)` look like? Just print it: ```python print(gfac_fc(5)) ``` shows ``` id ⚬ (*1) ⚬ (*2) ⚬ (*3) ⚬ (*4) ⚬ (*5) ```