The project is a library for functional programming in Rust.
* [fp-core.rs](#fp-corers)
* [installation](#installation)
* [functional programming jargon in rust](#functional-programming-jargon-in-rust)
# fp-core.rs
A library for functional programming in Rust.
It contains purely functional data structures to supplement the functional programming needs alongside
with the Rust Standard Library.
## Installation
Add below line to your Cargo.toml
```rust
fp-core = "0.1.9"
```
If you have [Cargo Edit](https://github.com/killercup/cargo-edit) you may simply
```bash
$ cargo add fp-core
```
# functional programming jargon in rust
Functional programming (FP) provides many advantages, and its popularity has been increasing as a result.
However, each programming paradigm comes with its own unique jargon and FP is no exception. By providing a glossary,
we hope to make learning FP easier.
Where applicable, this document uses terms defined in the [Fantasy Land spec](https://github.com/fantasyland/fantasy-land)
and Rust programming language to give code examples.
The content of this section was drawn from [Functional Programming Jargon in Javascript](https://github.com/hemanth/functional-programming-jargon) and
we sincerely appreciate them for providing the initial baseline.
__Table of Contents__
* [Arity](#arity)
* [Higher-Order Functions (HOF)](#higher-order-functions-hof)
* [Closure](#closure)
* [Partial Application](#partial-application)
* [Currying](#currying)
* [Auto Currying](#auto-currying)
* [Referential Transparency](#referential-transparency)
* [Lambda](#lambda)
* [Lambda Calculus](#lambda-calculus)
* [Purity](#purity)
* [Side effects](#side-effects)
* [Idempotent](#idempotent)
* [Function Composition](#function-composition)
* [Continuation](#continuation)
* [Point-Free Style](#point-free-style)
* [Predicate](#predicate)
* [Contracts](#contracts)
* [Category](#category)
* [Value](#value)
* [Constant](#constant)
* [Variance](#variance)
* [Higher Kinded Type](#higher-kinded-type-hkt)
* [Functor](#functor)
* [Pointed Functor](#pointed-functor)
* [Lifting](#lifting)
* [Equational Reasoning](#equational-reasoning)
* [Monoid](#monoid)
* [Monad](#monad)
* [Comonad](#comonad)
* [Applicative](#applicative)
* [Morphism](#morphism)
* [Endomorphism](#endomorphism)
* [Isomorphism](#isomorphism)
* [Homomorphism](#homomorphism)
* [Catamorphism](#catamorphism)
* [Hylomorphism](#hylomorphism)
* [Anamorphism](#anamorphism)
* [Setoid](#setoid)
* [Ord](#ord)
* [Semigroup](#semigroup)
* [Foldable](#foldable)
* [Lens](#lens)
* [Type Signature](#type-signature)
* [Algebraic data type](#algebraic-data-type)
* [Sum Type](#sum-type)
* [Product Type](#product-type)
* [Option](#option)
* [Functional Programming References](#functional-programming-references)
* [Function Programming development in Rust Language](#functional-programming-development-in-rust-language)
* [Inspiration](#inspiration)
## Arity
The number of arguments a function takes. From words like unary, binary, ternary, etc.
This word has the distinction of being composed of two suffixes, "-ary" and "-ity."
Addition, for example, takes two arguments, and so it is defined as a binary function or a function with an arity of two.
Such a function may sometimes be called "dyadic" by people who prefer Greek roots to Latin.
Likewise, a function that takes a variable number of arguments is called "variadic,"
whereas a binary function must be given two and only two arguments, currying and partial application notwithstanding (see below).
```rust
let sum = |a: i32, b: i32| { a + b }; // The arity of sum is 2
```
## Higher-Order Functions (HOF)
A function which takes a function as an argument and/or returns a function.
```rust
let filter = | predicate: fn(&i32) -> bool, xs: Vec | {
xs.into_iter().filter(predicate).collect::>()
};
```
```rust
let is_even = |x: &i32| { x % 2 == 0 };
```
```rust
filter(is_even, vec![1, 2, 3, 4, 5, 6]);
```
## Closure
A closure is a scope which retains variables available to a function when it's created. This is important for
[partial application](#partial-application) to work.
```rust
let add_to = |x: i32| move |y: i32| x + y;
```
We can call `add_to` with a number and get back a function with a baked-in `x`. Notice that we also need to move the ownership of the x to the internal lambda.
```rust
let add_to_five = add_to(5);
```
In this case the `x` is retained in `add_to_five`'s closure with the value `5`. We can then call `add_to_five` with the `y`
and get back the desired number.
```rust
add_to_five(3); // => 8
```
Closures are commonly used in event handlers so that they still have access to variables defined in their parents when they
are eventually called.
__Further reading__
* [Lambda Vs Closure](http://stackoverflow.com/questions/220658/what-is-the-difference-between-a-closure-and-a-lambda)
* [How do JavaScript Closures Work?](http://stackoverflow.com/questions/111102/how-do-javascript-closures-work)
## Partial Application
Partially applying a function means creating a new function by pre-filling some of the arguments to the original function.
To achieve this easily, we will be using a [partial application crate](https://crates.io/crates/partial_application)
```rust
#[macro_use]
extern crate partial_application;
fn foo(a: i32, b: i32, c: i32, d: i32, mul: i32, off: i32) -> i32 {
(a + b*b + c.pow(3) + d.pow(4)) * mul - off
}
let bar = partial!( foo(_, _, 10, 42, 10, 10) );
assert_eq!(
foo(15, 15, 10, 42, 10, 10),
bar(15, 15)
); // passes
```
Partial application helps create simpler functions from more complex ones by baking in data when you have it.
Curried functions are automatically partially applied.
__Further reading__
* [Partial Application in Haskell](https://wiki.haskell.org/Partial_application)
## Currying
The process of converting a function that takes multiple arguments into a function that takes them one at a time.
Each time the function is called it only accepts one argument and returns a function that takes one argument until all arguments are passed.
```rust
fn add(x: i32) -> impl Fn(i32)-> i32 {
move |y| x + y
}
let add5 = add(5);
add5(10); // 15
```
__Further reading__
* [Currying in Rust](https://hashnode.com/post/currying-in-rust-cjpfb0i2z00cm56s2aideuo4z)
## Auto Currying
Transforming a function that takes multiple arguments into one that if given less than its
correct number of arguments returns a function that takes the rest. When the function gets the correct number of
arguments it is then evaluated.
Although Auto Currying is not possible in Rust right now, there is a debate on this issue on the Rust forum:
https://internals.rust-lang.org/t/auto-currying-in-rust/149/22
## Referential Transparency
An expression that can be replaced with its value without changing the behavior of the program is said to be referentially transparent.
Say we have function greet:
```rust
let greet = || "Hello World!";
```
Any invocation of `greet()` can be replaced with `Hello World!` hence greet is referentially transparent.
## Lambda
An anonymous function that can be treated like a value.
```rust
fn increment(i: i32) -> i32 { i + 1 }
let closure_annotated = |i: i32| { i + 1 };
let closure_inferred = |i| i + 1;
```
Lambdas are often passed as arguments to Higher-Order functions.
You can assign a lambda to a variable, as shown above.
## Lambda Calculus
A branch of mathematics that uses functions to create a [universal model of computation](https://en.wikipedia.org/wiki/Lambda_calculus).
This is in contrast to a [Turing machine](https://www.youtube.com/watch?v=dNRDvLACg5Q), an equivalent model.
Lambda calculus has three key components: variables, abstraction, and application. A variable is just some
symbol, say `x`. An abstraction is sort of a function: it binds variables into "formulae". Applications
are function calls. This is meaningless without examples.
The identity function (`|x| x` in rust) looks like `\ x. x` in most literature (`\` is a Lambda where Latex
or Unicode make it available). It is an abstraction. If `1` were a value we could use, `(\ x. x) 1` would
be an application (and evaluating it gives you `1`).
But there's more...
__Computation in Pure Lambda Calculus__
Let's invent booleans. `\ x y. x` can be true and `\ x y. y` can be false.
If so, `\ b1 b2. b1(b2,(\\x y. y))` is `and`. Let's evaluate it to show how:
| `b1` | `b2` | Their `and` |
| --- | --- | --- |
| `\ x y. x` | `\\x y. x` | `\\x y. x` |
| `\ x y. x` | `\\x y. y` | `\\x y. y` |
| `\ x y. y` | `\\x y. y` | `\\x y. y` |
| `\ x y. y` | `\\x y. x` | `\\x y. y` |
I'll leave `or` as an exercise. Furthermore, `if` can now be implemented: `\c t e. c(t, e)` where `c` is the condition, `t`
the consequent (`then`) and `e` the else clause.
[SICP leaves numbers as an exercise.](https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-14.html#%_idx_1474)
They define 0 as `\f . \\x. x` and adding one as `\n. \f. \\x. f(n(f)(x))`.
That isn't even ASCII art, so let's add: `0 + 1`:
```
(\n. \f. \\x. f(n(f)(x)))(\f. \\x. x) = \f. \\x. f((\\x'. x')(x)) = \f. \\x. f(x)
```
Basically, the number of `f`s in the expression is the number. I'll leave figuring out larger numbers as a exercise.
With patience, you can show that `\f. \\x. f(f(x))` is two. This will help with addition: `\n m. \f. \\x. n(m(f)(x))`
should add two numbers. Let's make 4:
```
(\n m. \f. \\x. n(f)(m(f)(x)))(\f. x. f(f(x)), \f. \\x. f(f(x)))
= \f. \\x. (\f'. \\x'. f'(f'(x')))(f)((\f'. \\x'. f'(f'(x')))(f)(x))
= \f. \\x. (\\x'. f(f(x')))(f(f(x')))
= \f. \\x. f(f(f(f(x))))
```
Multiplication is harder and there's better
[exposition on Wikipedia](https://en.wikipedia.org/wiki/Church_encoding#Calculation_with_Church_numerals).
Another good reference is [on stackoverflow](https://stackoverflow.com/questions/3077908/church-numeral-for-addition).
## Purity
A function is pure if the return value is only determined by its input values, and does not produce side effects.
```rust
let greet = |name: &str| { format!("Hi! {}", name) };
greet("Jason"); // Hi! Jason
```
As opposed to each of the following:
```rust
let name = "Jason";
let greet = || -> String {
format!("Hi! {}", name)
};
greet(); // String = "Hi! Jason"
```
The above example's output is based on data stored outside of the function...
```rust
let mut greeting: String = "".to_string();
let mut greet = |name: &str| {
greeting = format!("Hi! {}", name);
};
greet("Jason");
assert_eq!("Hi! Jason", greeting); // Passes
```
... and this one modifies state outside of the function.
## Side effects
A function or expression is said to have a side effect if apart from returning a value,
it interacts with (reads from or writes to) external mutable state.
```rust
use std::time::SystemTime;
let now = SystemTime::now();
```
```rust
println!("IO is a side effect!");
// IO is a side effect!
```
## Idempotent
A function is idempotent if reapplying it to its result does not produce a different result.
```rust
// Custom immutable sort method
let sort = |x: Vec| -> Vec {
let mut x = x;
x.sort();
x
};
```
Then we can use the sort method like
```rust
let x = vec![2 ,1];
let sorted_x = sort(sort(x.clone()));
let expected = vec![1, 2];
assert_eq!(sorted_x, expected); // passes
```
```rust
let abs = | x: i32 | -> i32 {
x.abs()
};
let x: i32 = 10;
let result = abs(abs(x));
assert_eq!(result, x); // passes
```
## Function Composition
The act of putting two functions together to form a third function where the output of one function is the input of the other.
Below is an example of compose function is Rust.
```rust
macro_rules! compose {
( $last:expr ) => { $last };
( $head:expr, $($tail:expr), +) => {
compose_two($head, compose!($($tail),+))
};
}
fn compose_two(f: F, g: G) -> impl Fn(A) -> C
where
F: Fn(A) -> B,
G: F