1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
//! # Applicative functors? What is it about?
//!
//! You don't need to read/understand this chapter in order to use the library but it might
//! help to understand what makes it tick.
//! ## Category theory
//!
//! Category theory, also called Abstract Nonsense, is a general theory about mathematical
//! structures and their relations. *Category* in CT constists of two sorts of abstractions:
//! *objects* and *morphisms* along with some extra rules:
//! - objects don't expose any information other than the name and only serve as start and end points for morphisms
//! - morphisms must compose with associative composition
//! - there must be an *identity morphism* for every object that maps the object to itself
//!
//! A simple example of a category would be a category where objects are Rust types (here: `u8` ..
//! `u64`) and morphisms are functions between those types (here: `a`, `b` and `c`):
//!
//! ```rust
//! fn a(i: u8) -> u16 {
//! 3000 + i as u16
//! }
//!
//! fn b(i: u16) -> u32 {
//! 40000 + i as u32
//! }
//!
//! fn c(i: u32) -> u64 {
//! 40000 + i as u64
//! }
//!
//! /// Identity morphism
//! fn id<T>(i: T) -> T {
//! i
//! }
//!
//! /// morphism composition:
//! /// `comp (a, comp(b, c))` gives the same results as `comp(comp(a, b), c)`
//! fn comp<F, G, A, B, C>(f: F, g: G) -> impl Fn(A) -> C
//! where
//! F: Fn(A) -> B,
//! G: Fn(B) -> C,
//! {
//! move |i| g(f(i))
//! }
//! ```
//! ## Composition and decomposition
//!
//! Decomposition is one of the keys to solving big problems - you break down big problem into a
//! bunch of small problems, solve them separately and compose back a solution. Decomposition is
//! not required by computers but makes it easier to think about a problem: magical number for
//! human short term memory is 7 plus minus 2 objects. Category theory, studies relations and
//! composition can be a valuable tool: after all decomposition only makes sense when you can
//! combine components back into a solution. Imperative algorithms that operate in terms of
//! mutating variables are harder decompose - individual pieces need to be aware of the variables,
//! functional and declarative approaches make it easier: calculating a sum of all the numbers in a
//! vector can be decomposed into running an iterator over it and applying `fold` to it: `fold`
//! doesn't need to know about iteration shape, iterator doesn't need to know about how values are
//! used.
//!
//! In category theory you are not allowed to look inside the objects at all and can distinguish
//! between them only by means of the composition so as long as implemented API obeys the
//! restrictions set by category theory - it should be very composable.
//! ## Functors
//!
//! Let's start by talking about what a `Functor` is. Wikipedia defines it as a "design pattern
//! that allows for a generic type to apply a function inside without changing the structure of
//! the generic type". Sounds scary, but in Rust terms it's a trait that takes a value or values
//! in a container (or more general *value in a context* ) such as `Option<A>` and a function
//! `fn(A) -> B` and gives you `Option<B>` back.
//!
//! Closest analogy in a real code you can write in Rust right now would be modifying an `Option`
//! using only `Option::map`:
//! ```rust
//! fn plus_one(input: Option<u32>) -> Option<u32> {
//! input.map(|i| i + 1)
//! }
//!
//! let present = Some(10);
//! let absent = None;
//!
//! assert_eq!(plus_one(present), Some(11));
//! assert_eq!(plus_one(absent), None);
//! ```
//!
//! `Vec`, `Result` and other types that implement `map` are `Functors` as well, but `Functor`
//! is not limited just to containers - you don't have to have a value inside to be able to
//! manipulate it. In fact a regular rust function is also a `Functor` if you squint hard enough.
//! Consider `Reader` that allows you to perform transformations on a *value in a context* `T`
//! without having any value until it the execution time:
//!
//! ```rust
//! struct Reader<T>(Box<dyn Fn(T) -> T>);
//! impl<T: 'static> Reader<T> {
//! /// Initialize an new value in a context
//! fn new() -> Self {
//! Self(Box::new(|x| x))
//! }
//!
//! /// Modify a value in a context
//! fn map<F: Fn(T) -> T + 'static>(self, f: F) -> Self {
//! Self(Box::new(move |x| f((self.0)(x))))
//! }
//!
//! /// Apply the changes by giving it the initial value
//! fn run(self, input: T) -> T {
//! (self.0)(input)
//! }
//! }
//!
//! let val = Reader::<u32>::new();
//! let val = val.map(|x| x + 1);
//! let res = val.run(10);
//! assert_eq!(res, 11);
//! ```
//!
//! Not all the collections are `Functors` - by `Functor` laws mapping the *value in context*
//! shouldn't change the shape so any collections where shape depends on a value, such as `HashSet`
//! or `BTreeSet` are out.
//! ## Applicative Functors
//!
//! `map` in `Functor` is limited to a single *value in a context*, `Applicative Functor` extends it
//! to operations combining multiple values, closest Rust analogy would be doing computations on
//! `Option` or `Result` using only `?`, having `Some`/`Ok` around the whole expression and not using `return`.
//! ```rust
//! fn add_numbers(input_a: Option<u32>, input_b: Option<u32>) -> Option<u32> {
//! Some(input_a? + input_b?)
//! }
//!
//! let present_1 = Some(10);
//! let present_2 = Some(20);
//! let absent = None;
//!
//! assert_eq!(add_numbers(present_1, present_2), Some(30));
//! assert_eq!(add_numbers(present_1, absent), None);
//! assert_eq!(add_numbers(absent, absent), None);
//! ```
//!
//! Similarly to `Functors`, `Applicative Functors` are not limited to containers and can
//! represent *a value in an arbitrary context*.
//!
//! `Try` trait (`?`) for `Option` and `Result` short circuits when it finds a missing value,
//! but `Applicative Functors` in general don't have to - in fact to implement dynamic completion
//! `bpaf` needs to check items past the first failure point to collect all the possible
//! completions.
//! ## Alternative Functors
//!
//! So far `Applicative Functors` allow us to create structs containing multiple fields out of
//! individual parsers for each field. `Alternative` extends `Applicative` with two extra
//! things: one for combining two *values in a context* into one and and an idenity element
//! for this operation. In Rust a closest analogy would be `Option::or` and `Option::None`:
//!
//! ```rust
//! fn pick_number(a: Option<u32>, b: Option<u32>) -> Option<u32> {
//! a.or(b)
//! }
//!
//! let present_1 = Some(10);
//! let present_2 = Some(20);
//! let empty = None;
//! assert_eq!(pick_number(present_1, present_2), present_1);
//! assert_eq!(pick_number(present_1, empty), present_1);
//! assert_eq!(pick_number(empty, present_1), present_1);
//! assert_eq!(pick_number(empty, empty), empty);
//! ```
//! ## `Parser` trait and `construct!` macro
//!
//! [`Parser`] trait defines a context for values and gives access to `Functor` laws and [`construct!`]
//! macro allows to compose several values according to `Applicative` and `Alternative` laws.
//! ## So why use `Applicative Functors` then?
//!
//! As a user I want to be able to express requirements using full power of Rust algebraic
//! datatypes: `struct` for product types and `enum` for sum types. To give an example -
//! `cargo-show-asm` asks user to specify what to output - Intel or AT&T asm, LLVM or Rust's MIR
//! and opts to represent it as one of four flags: `--intel`, `--att`, `--llvm` and `--mir`. While
//! each flag can be though of a boolean value - present/absent - consuming it as an `enum` with four
//! possible values is much more convenient compared to a struct-like thing that can have any
//! combination of the flags inside:
//!
//! ```no_check
//! /// Format selection as enum - program needs to deal with just one format
//! enum Format {
//! Intel,
//! Att,
//! Llvm,
//! Mir
//! }
//!
//! /// Format selection as struct - can represent any possible combination of formats
//! struct Formats {
//! intel: bool,
//! att: bool,
//! llvm: bool,
//! mir: bool,
//! }
//! ```
//!
//! `Applicative` interface gives just enough power to compose simple parsers as an arbitrary tree
//! ready for consumption.
//!
//! As a library author I need to be able to extract information from the tree constructed by user
//! to generate `--help` information and do command line completion. As long as the tree uses only
//! `Applicative` powers - it is possible to evaluate it without giving it any input.
//! Adding `Monadic` powers (deciding what to parse next depending on the previous input) would
//! make this impossible.
//!
//! So `Applicative Functors` sits right in the middle between what users want to express and
//! library can consume.
//!
//! To recap - all sorts of Functors listed here only define laws to how individual parts are
//! composed, how values in context can be transformed and how pure values can be turned into a
//! functor, but not how the values are parsed or how they can be extracted.
//! ## Putting the values into a context
//!
//! Similarly to how `Reader` defined above `bpaf`'s `Parsers` don't actually have values inside
//! until they are executed. Instead starting points ([`flag`](NamedArg::flag), [`positional`],
//! [`argument`](NamedArg::argument), etc) define what exactly needs to be consumed, various mapping
//! functions define transformations, [`construct!`] composes them and defines the relative order
//! values should be consumed. Not everything present inside [`Parser`] can be repesented in terms
//! of plain applicative functors - specifically [`parse`](Parser::parse) is not and it is best
//! though of as a function that takes one applicative and gives a different applicative back.
//! The actual values will show up inside once `bpaf` starts running the [`OptionParser`] with
//! [`run`](OptionParser::run).
//! ## Taking the results out
//!
//! The rest of the execution is relatively simple: getting console arguments from OS, doing the
//! initial split into short/long flags and standalone words, disambiguating groups of short
//! options from short options with attached values and applying all the transformations like
//! `Reader::run` above would do.
#[cfg(doc)]
use crate::*;