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 Func-wrapped functions
Function combinators
Lambda expressions
Operator sections
Printing of Func values
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: fpower(f, 0)(x) = x, fpower(f, n)(x) = fpower(f, n-1)(f(x)) = f(fpower(f, n-1)(x)); prints as ‘**’)
fpower_left[A]: Func[Both[Func[A, A], int], Func[A, A]] (iterated function application, iterated 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
fexp[A, B, C, D]:Func[Both[Func[A, B], Func[C, D]], Func[Func[D, A], Func[C, B]]] (functorial exponentiation: fexp(f, g)(h) = f @ h @ g; prints as ‘^’)

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__`	**
`^`	`fexp`	`__xor__`, `__xor__`	^

For these function combinators to be recognized, both of the functions involved must have been wrapped in Func.

N.B. In an earlier version, the other function (if applicable) could be a plain function, which would then automatically be wrapped in Func. But it is then too easy to accidentally mistype id_ as id without getting a warning.

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 Function 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 Functions 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

from FuPy.basics import *
from operator import add, mul

_ = x_

Also see demo.py.

Operator sections and lambda abstraction

Let’s define some simple functions using operator sections and a lambda abstraction:

inc = (_ + 1)  # increment by one
dbl = (2 * _)  # double
sqr = la('x: x * x')  # square

Function combinators

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

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

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:

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.

@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

trace(lambda: fac(3), live=True)

which results in the following output, using Math notation:

Apply:     ┌ fac.3
Motivate:  =   { def. of fac }
Apply:     │     ┌ fac.2
Motivate:  │     =   { def. of fac }
Apply:     │     │     ┌ fac.1
Motivate:  │     │     =   { def. of fac }
Apply:     │     │     │     ┌ fac.0
Motivate:  │     │     │     =   { def. of fac }
Return:    │     │     │     └ 1
Apply:     │     │     │     ┌ mul.(1, 1)
Motivate:  │     │     │     =   { def. of mul }
Return:    │     │     │     └ 1
Return:    │     │     └ 1
Apply:     │     │     ┌ mul.(2, 1)
Motivate:  │     │     =   { def. of mul }
Return:    │     │     └ 2
Return:    │     └ 2
Apply:     │     ┌ mul.(3, 2)
Motivate:  │     =   { def. of mul }
Return:    │     └ 6
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

pre_fac = la('x: (const(1) | mul @ (id_ & (x @ (_ - 1)))) @ guard(_ == 0)').define_as("pre_fac")

Then apparently fac satisfies the equation

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.

Here is a trace of pre_fac(const(2))(3) (some details have been suppressed):

Apply:     ┌ pre_fac.(2°)
Motivate:  =   { def. of pre_fac }
Apply:     │     ┌ (λ x: `(const(1) | mul @ (id_ & x @ (_ - 1))) @ guard(_ == 0)`).(2°)
Motivate:  │     =   { def. of λ }
Return:    │     └ (1° ▽ mul* ⚬ (id △ 2° ⚬ (-1))) ⚬ (=0)?
Return:    └ (1° ▽ mul* ⚬ (id △ 2° ⚬ (-1))) ⚬ (=0)?
Apply:     ┌ ((1° ▽ mul* ⚬ (id △ 2° ⚬ (-1))) ⚬ (=0)?).3
Motivate:  =   { def. of ⚬ }
Apply:     │     ┌ ((=0)?).3
Motivate:  │     =   { def. of ? }
Apply:     │     │     ┌ (=0).3
Motivate:  │     │     =   { def. of (=0) }
Return:    │     │     └ False
Return:    │     └ Right(value=3)
Apply:     │     ┌ (1° ▽ mul* ⚬ (id △ 2° ⚬ (-1))).Right(value=3)
Motivate:  │     =   { def. of ▽ }
Apply:     │     │     ┌ (mul* ⚬ (id △ 2° ⚬ (-1))).3
Motivate:  │     │     =   { def. of ⚬ }
Apply:     │     │     │     ┌ (id △ 2° ⚬ (-1)).3
Motivate:  │     │     │     =   { def. of △ }
Apply:     │     │     │     │     ┌ id.3
Motivate:  │     │     │     │     =   { def. of id }
Return:    │     │     │     │     └ 3
Apply:     │     │     │     │     ┌ (2° ⚬ (-1)).3
Motivate:  │     │     │     │     =   { def. of ⚬ }
Apply:     │     │     │     │     │     ┌ (-1).3
Motivate:  │     │     │     │     │     =   { def. of (-1) }
Return:    │     │     │     │     │     └ 2
Apply:     │     │     │     │     │     ┌ (2°).2
Motivate:  │     │     │     │     │     =   { def. of ° }
Return:    │     │     │     │     │     └ 2
Return:    │     │     │     │     └ 2
Return:    │     │     │     └ (3, 2)
Apply:     │     │     │     ┌ mul.(3, 2)
Motivate:  │     │     │     =   { def. of mul; auto-unpack arguments from tuple }
Return:    │     │     │     └ 6
Return:    │     │     └ 6
Return:    │     └ 6
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

tfac(n) = (fac(n), n + 1)

This can be written pointfree as an equation on functions by using the split combinator and operator sectioning:

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

@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):
Apply:     ┌ tfac.3
Motivate:  =   { def. of tfac }
Apply:     │     ┌ ((mul △ (+1) ⚬ ≫)^3).(1, 1)
Motivate:  │     =   { def. of ^; auto-pack arguments in tuple }
Apply:     │     │     ┌ ((mul △ (+1) ⚬ ≫)^2).(1, 1)
Motivate:  │     │     =   { def. of ^ }
Apply:     │     │     │     ┌ (mul △ (+1) ⚬ ≫).(1, 1)
Motivate:  │     │     │     =   { def. of △ }
Apply:     │     │     │     │     ┌ mul.(1, 1)
Motivate:  │     │     │     │     =   { def. of mul; auto-unpack arguments from tuple }
Return:    │     │     │     │     └ 1
Apply:     │     │     │     │     ┌ ((+1) ⚬ ≫).(1, 1)
Motivate:  │     │     │     │     =   { def. of ⚬ }
Apply:     │     │     │     │     │     ┌ ≫.(1, 1)
Motivate:  │     │     │     │     │     =   { def. of ≫ }
Return:    │     │     │     │     │     └ 1
Apply:     │     │     │     │     │     ┌ (+1).1
Motivate:  │     │     │     │     │     =   { def. of (+1) }
Return:    │     │     │     │     │     └ 2
Return:    │     │     │     │     └ 2
Return:    │     │     │     └ (1, 2)
Apply:     │     │     │     ┌ (mul △ (+1) ⚬ ≫).(1, 2)
Motivate:  │     │     │     =   { def. of △ }
Apply:     │     │     │     │     ┌ mul.(1, 2)
Motivate:  │     │     │     │     =   { def. of mul; auto-unpack arguments from tuple }
Return:    │     │     │     │     └ 2
Apply:     │     │     │     │     ┌ ((+1) ⚬ ≫).(1, 2)
Motivate:  │     │     │     │     =   { def. of ⚬ }
Return:    │     │     │     │     └ 3
Return:    │     │     │     └ (2, 3)
Return:    │     │     └ (2, 3)
Apply:     │     │     ┌ (mul △ (+1) ⚬ ≫).(2, 3)
Motivate:  │     │     =   { def. of △ }
Apply:     │     │     │     ┌ mul.(2, 3)
Motivate:  │     │     │     =   { def. of mul; auto-unpack arguments from tuple }
Return:    │     │     │     └ 6
Apply:     │     │     │     ┌ ((+1) ⚬ ≫).(2, 3)
Motivate:  │     │     │     =   { def. of ⚬ }
Return:    │     │     │     └ 4
Return:    │     │     └ (6, 4)
Return:    │     └ (6, 4)
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:

@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). One can calculate the following definition for gfac_fc:

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

print(gfac_fc(5))

shows

id ⚬ (*1) ⚬ (*2) ⚬ (*3) ⚬ (*4) ⚬ (*5)

Basics

Contents

Predefined types

Predefined Func-wrapped functions

Function combinators

Operator precedence

Lambda expressions

Operator sections

Printing of Func values

Examples

Operator sections and lambda abstraction

Function combinators

Factorial

Factorial with function combinators

Tupled factorial

Flipped curried generalized factorial

Predefined `Func`-wrapped functions

Printing of `Func` values