## File: README.md
C# Functional Programming Language Extensions
=============================================
This library uses and abuses the features of C# to provide a pure functional-programming framework that, if you squint, can look like
extensions to the language itself. The desire here is to make programming in C# much more robust by helping the engineer's inertia flow
in the direction of declarative and pure functional code rather than imperative. Using these techniques for large code-bases can bring
tangible benefits to long-term maintenance by removing hidden complexity and by easing the engineer's and team's cognitive load.
[](https://github.com/louthy/language-ext/discussions)
__Author on...__
* __Blog__: [Notes from a Small Functional Island](https://paullouth.com/)
* __Bluesky__: [@paullouth.bsky.social](https://bsky.app/profile/paullouth.bsky.social)
* __Mastodon:__ [@louthy@4four.org](https://4four.org/@louthy)
* __Github ReadME project__: ['Functional programming is finally going mainstream'](https://github.com/readme/featured/functional-programming)
## Contents
* [Reference](#reference)
* [Nu-get package](#nu-get)
* [Getting started](#getting-started)
* [Prologue](#prologue)
* [**Features**](#features)
* [Functional effects and IO](#functional-effects-and-io)
* [Atomic concurrency, shared state, and collections](#atomic-concurrency-and-collections)
* [Immutable collections](#immutable-collections)
* [Functional streams](#functional-streams)
* [Optional and Alternative value monads](#optional-and-alternative-value-monads)
* [State managing monads](#state-managing-monads)
* [Parser combinators](#parser-combinators)
* [Pretty: Produce nicely formatted text with smart layouts](#pretty)
* [Differencing](#differencing)
* [Traits](#traits)
* [Value traits](#value-traits)
* [Contributing & Code of Conduct](#contributing--code-of-conduct)
## Reference
* [API Reference](https://louthy.github.io/language-ext/)
* [Issues that contain documentation and examples](https://github.com/louthy/language-ext/issues?utf8=%E2%9C%93&q=is%3Aissue%20label%3A%22examples%20%2F%20documentation%22%20)
## Nu-get
Nu-get package | Description
---------------|-------------
[LanguageExt.Parsec](https://www.nuget.org/packages/LanguageExt.Parsec) | Port of the [Haskell parsec library](https://hackage.haskell.org/package/parsec)
[LanguageExt.Streaming](https://www.nuget.org/packages/LanguageExt.Streaming) | A set of compositional streaming types
[LanguageExt.FSharp](https://www.nuget.org/packages/LanguageExt.FSharp) | F# to C# interop package. Provides interop between the LanguageExt.Core types (like `Option`, `List` and `Map`) to the F# equivalents, as well as interop between core BCL types and F#
[LanguageExt.Parsec](https://www.nuget.org/packages/LanguageExt.Parsec) | Port of the [Haskell parsec library](https://hackage.haskell.org/package/parsec)
[LanguageExt.Rx](https://www.nuget.org/packages/LanguageExt.Rx) | Reactive Extensions support for various types within the Core
[LanguageExt.Sys](https://www.nuget.org/packages/LanguageExt.Sys) | Provides an effects wrapper around the .NET System namespace making common IO operations pure and unit-testable
## Getting started
To use this library, simply include `LanguageExt.Core.dll` in your project or grab it from NuGet. It is also worth setting up some `global using` for your project. This is the full list that will cover all functionality and bring it into scope:
```C#
global using LanguageExt;
global using LanguageExt.Common;
global using LanguageExt.Traits;
global using LanguageExt.Effects;
global using LanguageExt.Streaming;
global using LanguageExt.Pretty;
global using LanguageExt.Traits.Domain;
global using static LanguageExt.Prelude;
```
A minimum, might be:
```c#
global using LanguageExt;
global using static LanguageExt.Prelude;
```
The namespace `LanguageExt` contains most of the core types; `LanguageExt.Prelude` contains the functions that bring into scope the prelude functions that behave like standalone functions in ML style functional programming languages; `LanguageExt.Traits` brings in the higher-kinded trait-types and many extensions; `LanguageExt.Common` brings in the `Error` type and predefined `Errors`.
## Prologue
From C# 6 onwards we got the ability to treat static classes like namespaces. This means that we can use static
methods without qualifying them first. That instantly gives us access to single term method names that look exactly like functions
in ML-style functional languages. i.e.
```C#
using static System.Console;
WriteLine("Hello, World");
```
This library tries to bring some of the functional world into C#. It won't always sit well with the seasoned C# OO programmer,
especially the choice of `camelCase` names for a lot of functions and the seeming 'globalness' of a lot of the library.
I can understand that much of this library is non-idiomatic, but when you think of the journey C# has been on, is "idiomatic"
necessarily right? A lot of C#'s idioms are inherited from Java and C# 1.0. Since then we've had generics, closures, Func, LINQ,
async... C# as a language is becoming more and more like a functional language on every release. In fact, the bulk of the new
features are either inspired by or directly taken from features in functional languages. So perhaps it's time to move the C#
idioms closer to the functional world's idioms?
My goal with this library is very much to create a whole new community within the larger C# community. This community is not
constrained by the dogma of the past or by the norms of C#. It understands that the OOP approach to programming has some problems
and tries to address them head-on.
And for those that say "just use F#" or "just use Haskell", sure, go do that. But it's important to remember that C# has a lot
going for it:
* Incredible investment into a state-of-the art compiler
* Incredible tooling (Visual Studio and Rider)
* A large ecosystem of open-source libraries
* A large community of developers already using it
* This is also very important for companies that hire engineers
* It _is_ a functional programming language! It has first-class functions, lambdas, etc.
* And with this library it has a functional-first _Base Class Library_
### A note about naming
One of the areas that's likely to get seasoned C# heads worked up is my choice of naming style. The intent is to try and make
something that _feels_ like a functional language rather than following rules of naming conventions (mostly set out by
the BCL).
There is, however, a naming guide that will keep you in good stead while reading through this documentation:
* Type names are `PascalCase` in the normal way
* The types all have constructor functions rather than public constructors that you instantiate with `new`. They will always
be `PascalCase`:
```C#
Option x = Some(123);
Option y = None;
Seq items = Seq(1,2,3,4,5);
List items = List(1,2,3,4,5);
HashMap dict = HashMap((1, "Hello"), (2, "World"));
Map dict = Map((1, "Hello"), (2, "World"));
```
* Any (non-type constructor) static function that can be used on its own by `using static LanguageExt.Prelude` are `camelCase`.
```C#
var x = map(opt, v => v * 2);
```
* Any extension methods, or anything "fluent" are `PascalCase` in the normal way
```C#
var x = opt.Map(v => v * 2);
```
Even if you disagree with this non-idiomatic approach, all of the `camelCase` static functions have fluent variants, so you never actually have to see the non-standard stuff.
## Features
### [Functional effects and IO](https://louthy.github.io/language-ext/LanguageExt.Core/Effects/index.html)
| Location | Feature | Description |
|----------|--------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| `Core` | `IO` | [A synchronous and asynchronous side-effect: an IO monad](https://louthy.github.io/language-ext/LanguageExt.Core/Effects/IO/index.html) |
| `Core` | `Eff` | [A synchronous and asynchronous side-effect with error handling](https://louthy.github.io/language-ext/LanguageExt.Core/Effects/Eff/Eff%20no%20runtime/index.html) |
| `Core` | `Eff` | [Same as `Eff` but with an injectable runtime for dependency-injection: a unit testable IO monad](https://louthy.github.io/language-ext/LanguageExt.Core/Effects/Eff/Eff%20with%20runtime/index.html) |
### [Atomic concurrency and collections](https://louthy.github.io/language-ext/LanguageExt.Core/Concurrency/index.html)
| Location | Feature | Description |
|----------|------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------|
| `Core` | `Atom` | [A lock-free atomically mutable reference for working with shared state](https://louthy.github.io/language-ext/LanguageExt.Core/Concurrency/Atom) |
| `Core` | `Ref` | [An atomic reference to be used in the transactional memory system](https://louthy.github.io/language-ext/LanguageExt.Core/Concurrency/STM) |
| `Core` | `AtomHashMap` | [An immutable `HashMap` with a lock-free atomically mutable reference](https://louthy.github.io/language-ext/LanguageExt.Core/Concurrency/AtomHashMap) |
| `Core` | `AtomSeq` | [An immutable `Seq` with a lock-free atomically mutable reference](https://louthy.github.io/language-ext/LanguageExt.Core/Concurrency/AtomSeq) |
| `Core` | `VectorClock` | [Understand distributed causality](https://louthy.github.io/language-ext/LanguageExt.Core/Concurrency/VectorClock) |
| `Core` | `VersionVector` | [A vector clock with some versioned data](https://louthy.github.io/language-ext/LanguageExt.Core/Concurrency/VersionVector) |
| `Core` | `VersionHashMap ` | [Distrubuted atomic versioning of keys in a hash-map](https://louthy.github.io/language-ext/LanguageExt.Core/Concurrency/VersionHashMap) |
### [Immutable collections](https://louthy.github.io/language-ext/LanguageExt.Core/Immutable%20Collections/index.html)
| Location | Feature | Description |
|----------|----------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| `Core` | `Arr` | [Immutable array](https://louthy.github.io/language-ext/LanguageExt.Core/Immutable%20Collections/Arr/index.html) |
| `Core` | `Seq` | [Lazy immutable list, evaluate at-most-once](https://louthy.github.io/language-ext/LanguageExt.Core/Immutable%20Collections/Seq/index.html) - very, very fast! |
| `Core` | `Iterable` | [Wrapper around `IEnumerable` with support for traits](https://louthy.github.io/language-ext/LanguageExt.Core/Immutable%20Collections/Iterable/index.html) - enables the higher-kinded traits to work with enumerables. |
| `Core` | `Lst` | [Immutable list](https://louthy.github.io/language-ext/LanguageExt.Core/Immutable%20Collections/List/index.html) - use `Seq` over `Lst` unless you need `InsertAt` |
| `Core` | `Map` | [Immutable map](https://louthy.github.io/language-ext/LanguageExt.Core/Immutable%20Collections/Map/index.html) |
| `Core` | `Map` | [Immutable map with Ord constraint on `K`](https://louthy.github.io/language-ext/LanguageExt.Core/Immutable%20Collections/Map/index.html) |
| `Core` | `HashMap` | [Immutable hash-map](https://louthy.github.io/language-ext/LanguageExt.Core/Immutable%20Collections/HashMap/index.html) |
| `Core` | `HashMap` | [Immutable hash-map with Eq constraint on `K`](https://louthy.github.io/language-ext/LanguageExt.Core/Immutable%20Collections/HashMap/index.html) |
| `Core` | `Set` | [Immutable set](https://louthy.github.io/language-ext/LanguageExt.Core/Immutable%20Collections/Set/index.html) |
| `Core` | `Set` | [Immutable set with Ord constraint on `A`](https://louthy.github.io/language-ext/LanguageExt.Core/Immutable%20Collections/Set/index.html) |
| `Core` | `HashSet` | [Immutable hash-set](https://louthy.github.io/language-ext/LanguageExt.Core/Immutable%20Collections/HashSet/index.html) |
| `Core` | `HashSet` | [Immutable hash-set with Eq constraint on `A`](https://louthy.github.io/language-ext/LanguageExt.Core/Immutable%20Collections/HashSet/index.html) |
| `Core` | `Que` | [Immutable queue](https://louthy.github.io/language-ext/LanguageExt.Core/Immutable%20Collections/Queue/index.html) |
| `Core` | `Stck` | [Immutable stack](https://louthy.github.io/language-ext/LanguageExt.Core/Immutable%20Collections/Stack/index.html) |
### [Functional streams](https://louthy.github.io/language-ext/LanguageExt.Streaming/index.html)
| Location | Feature | Description |
|----------|--------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| `Streaming` | Pipes | [Connect reusable streaming components into a closed effect](https://louthy.github.io/language-ext/LanguageExt.Streaming/Pipes/) |
| `Streaming` | `Sink` | [Entry point to a channel. Sinks receive values and propagate them through a channel](https://louthy.github.io/language-ext/LanguageExt.Streaming/Sink/) |
| `Streaming` | `SinkT` | [As above but with effects](https://louthy.github.io/language-ext/LanguageExt.Streaming/SinkT/) |
| `Streaming` | `Source` | [Stream of synchronous or asynchronous values depending on the construction. Values flow downstream and are aggregated with a reducer.](https://louthy.github.io/language-ext/LanguageExt.Streaming/Source/) |
| `Streaming` | `SourceT` | [As above but with effects](https://louthy.github.io/language-ext/LanguageExt.Streaming/SourceT/) |
| `Streaming` | `Conduit` | [Represents a channel with an internal queue. The conduit has a `Sink` and a `Source` allowing items to be posted into the conduit, co-mapped, mapped, and consumed.](https://louthy.github.io/language-ext/LanguageExt.Streaming/Conduit) |
| `Streaming` | `ConduitT` | [As above but with effects: the conduit has a `SinkT` and a `SourceT` allowing items to be posted into the conduit, co-mapped, mapped, and consumed.](https://louthy.github.io/language-ext/LanguageExt.Streaming/ConduitT) |
### [Optional and alternative value monads](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/Alternative%20Monads/index.html)
| Location | Feature | Description |
|----------|---------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| `Core` | `Option` | [Option monad](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/Alternative%20Monads/Option/index.html) |
| `Core` | `OptionT` | [Option monad-transformer](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/Alternative%20Monads/OptionT/index.html) |
| `Core` | `Either` | [Right/Left choice monad](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/Alternative%20Monads/Either/index.html) |
| `Core` | `EitherT` | [Right/Left choice monad-transformer](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/Alternative%20Monads/EitherT/index.html) |
| `Core` | `Fin` | [`Error` handling monad, like `Either`](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/Alternative%20Monads/Fin/index.html) |
| `Core` | `FinT` | [`Error` handling monad-transformer](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/Alternative%20Monads/FinT/index.html) |
| `Core` | `Try` | [Exception handling monad](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/Alternative%20Monads/Try/index.html) |
| `Core` | `TryT` | [Exception handling monad-transformer](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/Alternative%20Monads/TryT/index.html) |
| `Core` | `Validation` | [Validation applicative and monad](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/Alternative%20Monads/Validation/index.html) for collecting multiple errors before aborting an operation |
| `Core` | `ValidationT` | [Validation applicative and monad-transformer](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/Alternative%20Monads/ValidationT/index.html) |
### [State managing monads](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/State%20and%20Environment%20Monads/index.html)
| Location | Feature | Description |
|----------|--------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| `Core` | `Reader` | [Reader monad](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/State%20and%20Environment%20Monads/Reader/Reader/index.html) |
| `Core` | `ReaderT` | [Reader monad-transformer](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/State%20and%20Environment%20Monads/Reader/ReaderT/index.html) |
| `Core` | `Writer` | [Writer monad that logs to a `W` constrained to be a Monoid](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/State%20and%20Environment%20Monads/Writer/Writer/index.html) |
| `Core` | `WriterT` | [Writer monad-transformer](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/State%20and%20Environment%20Monads/Writer/WriterT/index.html) |
| `Core` | `State` | [State monad](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/State%20and%20Environment%20Monads/State/State/index.html) |
| `Core` | `StateT` | [State monad-transformer](https://louthy.github.io/language-ext/LanguageExt.Core/Monads/State%20and%20Environment%20Monads/State/StateT/index.html) |
### [Parser combinators](https://louthy.github.io/language-ext/LanguageExt.Parsec/index.html)
| Location | Feature | Description |
|----------|----------------|--------------------------------------------------------------------------------------------------------------------------------|
| `Parsec` | `Parser` | [String parser monad and full parser combinators library](https://louthy.github.io/language-ext/LanguageExt.Parsec/index.html) |
| `Parsec` | `Parser` | [Parser monad that can work with any input stream type](https://louthy.github.io/language-ext/LanguageExt.Parsec/index.html) |
### [Pretty](https://louthy.github.io/language-ext/LanguageExt.Core/Pretty/index.html)
| Location | Feature | Description |
|----------|----------|--------------------------------------------------|
| `Core` | `Doc` | Produce nicely formatted text with smart layouts |
### [Differencing](https://louthy.github.io/language-ext/LanguageExt.Core/DataTypes/Patch/index.html)
| Location | Feature | Description |
|----------|-----------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| `Core` | `Patch` | Uses patch-theory to efficiently calculate the difference (`Patch.diff(list1, list2)`) between two collections of `A` and build a patch which can be applied (`Patch.apply(patch, list)`) to one to make the other (think git diff). |
### [Traits](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/index.html)
The traits are major feature of `v5`+ language-ext that makes generic programming with higher-kinds a reality. Check out Paul's [series on Higher Kinds](https://paullouth.com/higher-kinds-in-c-with-language-ext/) to get a deeper insight.
| Location | Feature | Description |
|----------|----------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| `Core` | `Applicative` | [Applicative functor](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Applicative/index.html) |
| `Core` | `Eq` | [Ad-hoc equality trait](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Eq/index.html) |
| `Core` | `Fallible` | [Trait that describes types that can fail](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Fallible/index.html) |
| `Core` | `Foldable` | [Aggregation over a structure](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Foldable/index.html) |
| `Core` | `Functor` | [Functor `Map`](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Functor/index.html) |
| `Core` | `Has` | [Used in runtimes to enable DI-like capabilities](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Has/index.html) |
| `Core` | `Hashable` | [Ad-hoc has-a-hash-code trait](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Hashable/index.html) |
| `Core` | `Local` | [Creates a local environment to run a computation ](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Local/index.html) |
| `Core` | `Monad` | [Monad trait](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Monads/Monad/index.html) |
| `Core` | `MonadT` | [Monad transformer trait](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Monads/MonadT/index.html) |
| `Core` | `Monoid` | [A monoid is a type with an identity `Empty` and an associative binary operation `+`](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Monoid/index.html) |
| `Core` | `MonoidK` | [Equivalent of monoids for working on higher-kinded types](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/MonoidK/index.html) |
| `Core` | `Mutates` | [Used in runtimes to enable stateful operations](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Mutates/index.html) |
| `Core` | `Ord` | [Ad-hoc ordering / comparisons](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Ord/index.html) |
| `Core` | `Range` | [Abstraction of a range of values](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Range/index.html) |
| `Core` | `Readable` | [Generalised Reader monad abstraction](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Readable/index.html) |
| `Core` | `Semigroup` | [Provides an associative binary operation `+`](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Semigroup/index.html) |
| `Core` | `SemigroupK` | [Equivalent of semigroups for working with higher-kinded types](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/SemigroupK/index.html) |
| `Core` | `Stateful` | [Generalised State monad abstraction](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Stateful/index.html) |
| `Core` | `Traversable` | [Traversable structures support element-wise sequencing of Applicative effects](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Traversable/index.html) |
| `Core` | `Writable` | [Generalised Writer monad abstraction](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Writable/index.html) |
### [Value traits](https://louthy.github.io/language-ext/LanguageExt.Core/Traits/Domain/index.html)
These work a little like type-aliasing but they impart semantic meaning and some common operators for the underlying value.
| Location | Feature | Description |
|----------|--------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| `Core` | `DomainType` | Provides a mapping from `SELF` to an underlying representation: `REPR` |
| `Core` | `Identifier ` | Identifiers (like IDs in databases: `PersonId` for example), they are equivalent to `DomaintType` with equality. |
| `Core` | `VectorSpace` | Scalable values; can add and subtract self, but can only multiply and divide by a scalar. Can also negate. |
| `Core` | `Amount ` | Quantities, such as the amount of money in USD on a bank account or a file size in bytes. Derives `VectorSpace`, `IdentifierLike`, `DomainType`, and is orderable (comparable). |
| `Core` | `Locus ` | Works with space-like structures. Spaces have absolute and relative distances. Has an origin/zero point and derives `DomainType`, `IdentifierLike`, `AmountLike` and `VectorSpace`. `DISTANCE` must also be an `AmountLike`. |
_These features are still a little in-flux as of 17th Oct 2024 - they may evolve, be renamed, or removed - but I like the idea!_
## Further
For some non-reference like documentation:
* Paul's blog: [Notes from a Small Functional Island](https://paullouth.com/) does deep dives into the philosophy of FP and the inner-workings of language-ext.
* [The wiki](https://github.com/louthy/language-ext/wiki) has some additional documentation, some might be a little out of date since the big `v5` refactor, but should give some good insights.
## Contributing & Code of Conduct
If you would like to get involved with this project, please first read the [Contribution Guidelines](https://github.com/louthy/language-ext/blob/main/CONTRIBUTING.md) and the [Code of Conduct](https://github.com/louthy/language-ext/blob/main/CODE_OF_CONDUCT.md).
---
## File: LanguageExt.Core/Class Instances/README.md
__If you're new to this library or functional-programming this is almost certainly not the place to start browsing!__
Class-instances try to replicate the instances of Haskell in C#. They pair with the traits using ad-hoc polymorphism.
Ad-hoc polymorphism has long been believed to not be possible in C#. However with some cunning _it is_. Ad-hoc polymorphism allows
programmers to add traits to a type later. For example in C# it would be amazing if we had an interface called `INumeric` for numeric
types like `int`, `long`, `double`, etc. The reason this doesn't exist is if you write a function like:
INumeric Add(INumeric x, INumeric y) => x + y;
Then it would cause boxing. Which is slow (well, slower). I can only assume that's why it wasn't added by the BCL team. Anyway, it's
possible to create a numeric type, very much like a trait in Haskell, and ad-hoc instances of the numeric trait that allow
for generic numeric operations without boxing. [See the wiki for a deeper dive into ad-hoc polymorphism](https://github.com/louthy/language-ext/wiki/Ad-hoc-polymorphism)
---
## File: LanguageExt.Core/Common/README.md
## `Error`
The `Error` type works like a discriminated-union, it is an `abstract record` type with many sub-cases
(which are listed below). It is used extensively with various monadic types, like `Fin`, the
_Effect System_ monads of `Eff`, `Eff`, `Aff`, `Aff` and the compositional
streaming Pipes features.
> The reason they're buried in the `Common` namespace is because, `Error` is a common type name. And so, this gives
the programmer a chance to not include it when `using LanguageExt;`
`Error` exists because `Exception` is really only meant for _exceptional_ errors. However, in C#-land we've been trained
to throw them even for *expected* errors.
Instead we use `Error` to represent three key types of error:
* `Exceptional` - An unexpected error
* `Expected` - An expected error
* `ManyErrors` - Many errors (possibly zero)
These are the key base-types that indicate the *'flavour'* of the error. For example, a 'user not found' error isn't
something exceptional, it's something we expect *might* happen. An `OutOfMemoryException` however, *is*
exceptional - it should never happen, and we should treat it as such.
Most of the time we want sensible handling of expected errors, and bail out completely for something exceptional. We also want
to protect ourselves from information leakage. Leaking exceptional errors via public APIs is a surefire way to open up more
information to hackers than you would like. The `Error` derived types all try to protect against this kind of leakage without
losing the context of the type of error thrown.
Essentially an error is either created from an `Exception` or it isn't. This allows for expected errors to be
represented without throwing exceptions, but also it allows for more principled error handling. We can pattern-match on the
type, or use some of the built-in properties and methods to inspect the `Error`:
* `IsExceptional` - `true` for exceptional errors. For `ManyErrors` this is `true` if _any_ of the errors are exceptional.
* `IsExpected` - `true` for non-exceptional/expected errors. For `ManyErrors` this is `true` if _all_ of the errors are expected.
* `Is(E exception)` - `true` if the `Error` is exceptional and any of the the internal `Exception` values are of type `E`.
* `Is(Error error)` - `true` if the `Error` matches the one provided. i.e. `error.Is(Errors.TimedOut)`.
The `Error` type can be constructed to be exceptional or expected. For example, this is an expected error:
Error.New("This error was expected")
When expected errors are used with codes then equality and matching is done via the code only:
Error.New(404, "Page not found");
And this is an exceptional error:
try
{
// This wraps up the exceptional error
}
catch(Exception e)
{
return Error.New(e);
}
Finally, you can collect many errors:
Error.Many(Error.New("error one"), Error.New("error two"));
Or more simply:
Error.New("error one") + Error.New("error two")
You can extend the set of error types (perhaps for passing through extra data) by creating a new
record inherits `Exceptional` or `Expected`:
public record BespokeError(bool MyData)
: Expected("Something bespoke", 100, None);
By default the properties of the new error-type won't be serialised. So, if you want to pass a
payload over the wire, add the `[property: DataMember]` attribute to each member:
public record BespokeError([property: DataMember] bool MyData)
: Expected("Something bespoke", 100, None);
Using this technique it's trivial to create new error-types when additional data needs to be moved
around, but also there's a ton of built-in functionality for the most common use-cases.
---
## File: LanguageExt.Core/Concurrency/Atom/README.md
Atoms provide a way to manage shared, synchronous, independent state without locks. You can use them to wrap up immutable data structures
and then atomically update them using the various `Swap` methods, or read them by calling the `Value` property.
If a conflict is encountered during a `Swap` operation, the operation is re-run using the latest state, and so you should minimise the time
spent in the `Swap` function, as well as make sure there are no side-effects, otherwise all bets are off.
See the [concurrency section](https://github.com/louthy/language-ext/wiki/Concurrency) of the wiki for more info.
### Usage
record Person(string Name, string Surname);
// Create a new atom
var person = Atom(new Person("Paul", "Louth"));
// Modify it atomically
person.Swap(p => p with { Surname = $"{p.Name}y" });
// Take a snapshot of the state of the atom
var snapshot = p.Value;
---
## File: LanguageExt.Core/Concurrency/README.md
We prefer to work with immutable types in functional-programming. However, it's not always possible, and sometimes we
need some shared mutable state. With the immutable types in this library you'd need to protect the updates with locks:
// Some global
HashSet set = HashSet(1, 2, 3);
object sync = new();
lock(sync)
{
set = set.Add(4);
}
This in unsatisfactory, and so this module is all about lock-free atomic operations. `Atom` allows you to protect any
value. `AtomHashMap` and `AtomSeq` are `HashMap` and `Seq` wrapped up into a lock-free mutable structure. Snapshots
of those are free! The above code can be written:
AtomHashSet set = AtomHashSet(1, 2, 3);
set.Add(4);
Finally, there's the Software Transactional Memory (STM) system. Which allows for transactional changes to multiple
`Ref` values. `Ref` just wrap up access to a value, and allows the state changes to be tracked by the `STM`.
See the [concurrency section](https://github.com/louthy/language-ext/wiki/Concurrency) of the wiki for more info.
---
## File: LanguageExt.Core/DataTypes/README.md
These are all pure, immutable, data-types apart from `SpanArray`. `SpanArray` does almost exactly what the .NET `Span` does,
however this came first, and so will remain supported. It's not advised to use it.
---
## File: LanguageExt.Core/Effects/README.md
Effects are functorial, monadic, and applicative types that are designed to capture IO based side-effects.
| Section | Type | Description |
|----------------------|-----------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [`IO`](IO) | [`IO`](IO) | Asynchronous and synchronous IO. Captures side-effects, manages resources, but throws exceptions. The `IO` monad is the base of all IO based operations and should be used in your monad-transformer stacks when you need IO. |
| [`Eff`](Eff) | [`Eff`](Eff) | Asynchronous and synchronous IO. Captures side-effects, manages resources, handles exceptions elegantly. |
| [`Eff`](Eff) | [`Eff`](Eff) | Asynchronous and synchronous IO. Captures side-effects, manages resources, handles exceptions elegantly, and has an injectable runtime (`RT`) which can provide configuration and dependency-injection |
---
## File: LanguageExt.Core/Immutable Collections/IteratorAsync/README.md
`IteratorAsync` is a functional-wrapper for `IAsyncEnumerator`. The abstraction leaks a little, so it's worth
understanding how it works by reading the details below. On the whole it behaves like an immutable stream
that caches values as it goes, but there's some footguns that you should be aware of so that they can be
avoided.
## Problem: `IAsyncEnumerator`
* It is mutable which means using it in immutable data-structures is problematic.
* If you pass an `IAsyncEnumerator` reference to two threads, each thread can
call `MoveNext`and it will move the enumeration position for other thread, or even worse, move past the end
of the sequence due to race conditions.
* Enumerators start before the first item and use a complicated mechanism for accessing and testing the validity of
the element value.
_Nobody in their right mind would invent an interface like `IAsyncEnumerator` today._
## Solution: `IteratorAsync`
`IteratorAsync` still uses `IAsyncEnumerator` internally, but it makes it thread-safe and functional. From the outside
the type acts and works exactly like any other immutable sequence, but internally it does some quite complex
processing to achieve this with an `IAsyncEnumerator` reference.
> You may say "Why not just drop `IAsyncEnumerator`?" - which is a completely valid position to hold. Unfortunately,
> `IAsyncEnumerable` and `IAsyncEnumerator` are baked into the CPS state-machine that is used for `yield return` and
> `yield break`. So, we don't get to ignore those types, and instead we need to make them play nice.
`IAsyncEnumerable` has a method called `GetAsyncEnumerator()` which is used to access an `IAsyncEnumerator`. A new extension
method is available called `GetIteratorAsync()`, this will yield an `IteratorAsync`.
---
## File: LanguageExt.Core/Immutable Collections/Iterator/README.md
`Iterator` is a functional-wrapper for `IEnumerator`. The abstraction leaks a little, so it's worth
understanding how it works by reading the details below. On the whole, it behaves like an immutable stream
that caches values as it goes, but there are some footguns that you should be aware of so that they can be
avoided.
## Problem: `IEnumerator`
* It is mutable which means using it in immutable data-structures is problematic.
* If you pass an `IEnumerator` reference to two threads, each thread can
call `MoveNext`and it will move the enumeration position for other thread, or even worse, move past the end
of the sequence due to race conditions.
* Enumerators start before the first item and use a complicated mechanism for accessing and testing the validity of
the element value.
_Nobody in their right mind would invent an interface like `IEnumerator` today._
## Solution: `Iterator`
`Iterator` still uses `IEnumerator` internally, but it makes it thread-safe and functional. From the outside
the type acts and works exactly like any other immutable sequence, but internally it does some quite complex
processing to achieve this with an `IEnumerator` reference.
> You may say "Why not just drop `IEnumerator`?" - which is a completely valid position to hold. Unfortunately,
> `IEnumerable` and `IEnumerator` are baked into the CPS state-machine that is used for `yield return` and
> `yield break`. So, we don't get to ignore those types, and instead we need to make them play nice.
`IEnumerable` has a method called `GetEnumerator()` which is used to access an `IEnumerator`. A new extension
method is available called `GetIterator()`, this will yield an `Iterator`.
You can pattern-match an `Iterator` like a functional 'cons' linked-list type:
```c#
static A Sum(Iterator iter) where A : INumber =>
iter switch
{
Iterator.Nil => A.Zero,
Iterator.Cons(var x, var xs) => x + Sum(xs),
}
```
Or, use `IsEmpty` and `Head`:
```c#
static A Sum(Iterator iter) where A : INumber =>
iter.IsEmpty
? A.Zero
: iter.Head + Sum(iter.Tail);
```
Or, use built-in operators:
```c#
static A Sum(Iterator iter) where A : INumber =>
iter.Fold(A.Zero, (s, x) => s + x);
```
Or, take an imperative approach:
```c#
static A Sum(Iterator iter) where A : INumber
{
var total = A.Zero;
while(!iter.IsEmpty)
{
total += iter.Head;
iter = iter.Tail;
}
return total;
}
```
And,
```c#
static A Sum(Iterator iter) where A : INumber
{
for(var total = A.Zero; !iter.IsEmpty; iter = iter.Tail)
{
total += iter.Head;
}
return total;
}
```
`Iterator` is `abstract` and the first type returned from `GetIterator()` will be a `Iterator.ConsFirst`, this type implements
`Iterator`. The internal fields that `ConsFirst` contains are these:
```c#
IEnumerable enumerable;
int firstAcquired;
Iterator? firstValue;
```
So, you can see that it doesn't actually have an `IEnumerator` as this point.
The two key properties of `Iterator` are `Head` (for accessing the current item) and `Tail` (for accessing
the remaining items), so let's look at those for `ConsFirst`:
```c#
public override A Head =>
First.Head;
public override Iterator Tail =>
First.Tail;
```
They both access `First`, which is:
```c#
Iterator First
{
get
{
if (firstAcquired == 2) return firstValue!;
SpinWait sw = default;
while (firstAcquired < 2)
{
if (Interlocked.CompareExchange(ref firstAcquired, 1, 0) == 0)
{
try
{
var enumerator = enumerable.GetEnumerator();
if (enumerator.MoveNext())
{
firstValue = new ConsValueEnum(enumerator.Current, enumerator);
}
else
{
enumerator.Dispose();
firstValue = Nil.Default;
}
firstAcquired = 2;
}
catch (Exception)
{
firstAcquired = 0;
throw;
}
}
else
{
sw.SpinOnce();
}
}
return firstValue!;
}
}
```
This all looks quite complex, but you should be able to see that the `Interlocked.CompareExchange`
then-block is where the `IEnumerator` is created. We then either set `firstValue` to a new `ConsValueEnum` with
the head-item and the `enumerator` as arguments; or we set it to `Nil`.
Upon success, we set `firstAcquired` to `2`. So, subsequent calls to `First` will just return `firstValue`. This
locking technique without using locks is a way to efficiently protect the enumerator from race-conditions.
So, upon first access to either `Head` or `Tail` we launch the `IEnumerator` and cache the first item in the sequence.
All subsequent access goes to `Head` or `Tail` on either `Nil` or `ConsValueEnum`. We never touch the `IEnumerator`
again in `ConsFirst`.
The `Nil` implementation isn't so surprising:
```c#
public override A Head =>
throw new InvalidOperationException("Nil iterator has no head");
public override Iterator Tail =>
this;
```
`ConsValueEnum` is where it gets interesting. It has the following internal fields:
```c#
Exception? exception;
IEnumerator? enumerator;
int tailAcquired;
Iterator? tailValue;
```
It also has a `Head` property that is set in the constructor:
```c#
public override A Head { get; }
```
So, we can access the `Head` value at any time, but the `Tail` value isn't yet set:
```c#
public override Iterator Tail
{
get
{
if(tailAcquired == 2) return tailValue!;
if(tailAcquired == 3) exception!.Rethrow();
SpinWait sw = default;
while (tailAcquired < 2)
{
if (Interlocked.CompareExchange(ref tailAcquired, 1, 0) == 0)
{
try
{
if (enumerator!.MoveNext())
{
tailValue = new ConsValueEnum(enumerator.Current, enumerator);
}
else
{
enumerator?.Dispose();
enumerator = null;
tailValue = Nil.Default;
}
tailAcquired = 2;
}
catch (Exception e)
{
exception = e;
tailAcquired = 3;
throw;
}
}
else
{
sw.SpinOnce();
}
}
if(tailAcquired == 3) exception!.Rethrow();
return tailValue!;
}
}
```
This does a similar thing to `ConsFirst` of protecting a section with `Interlocked.CompareExchange`. So, we can
only ever access the 'then' part [of that `if` statement] once. In that block we `MoveNext` the `IEnumerator`
which will either return `true` or `false`.
If `true` then we create another `ConsValueEnum`, if `false` then we use `Nil`. Whichever is created gets assigned
to `tailValue` and `tailAcquired` gets set to `2`. That means subsequent calls to `Tail` will just return
`tailValue`.
That process continues for each item of the sequence until the `IEnumerator` runs out of items to yield. The end
result is a linked-list of `ConsValueEnum` objects that have a `ConsFirst` object at the head of the linked-list.
So, `Iterator` effectively caches the sequence as you go. If you hold on to the head of the sequence, then the
whole list may end up in memory at once. This could be problematic when working with large lazy sequences or even
infinite sequences.
This, for example, is fine:
```c#
for(var iter = Naturals.GetIterator(); !iter.IsEmpty; iter = iter.Tail)
{
Console.WriteLine(iter.Head);
}
```
Because the `iter` reference keeps getting updated, in-place, meaning that nothing is holding on to the head-item in
the sequence, and so the garbage-collector can collect those unreferenced items.
Whereas this (below) will cause memory-usage to grow and grow:
```c#
var start = Naturals.GetIterator();
for(var iter = start; !iter.IsEmpty; iter = iter.Tail)
{
Console.WriteLine(iter.Head);
}
```
Because `start` is holding a reference to the first item, so it must hold a reference (indirectly) to every
subsequent item. Meaning the garbage-collector can't collect.
To get around this you can use `Clone`:
```c#
var start = Naturals.GetIterator();
for(var iter = start.Clone(); !iter.IsEmpty; iter = iter.Tail)
{
Console.WriteLine(iter.Head);
}
```
This creates a new 'head' for the sequence and so `iter` is the only reference, meaning updates to `iter`
make the head elements free for garbage collection.
So, `Iterator` is much, much more powerful than `IEnumerator`. It is mostly useful for immutable data-types
that need to carry an `IEnumerator`, but can't due to its mutable-limitations. `Iterator` has some limitations of
its own, but they are relatively easy to work around, whereas that isn't the case with `IEnumerator` (without writing
a type like `Iterator`!).
---
## File: LanguageExt.Core/Immutable Collections/README.md
This a suite of [very high-performance immutable-collections](https://github.com/louthy/language-ext/blob/main/Performance.md).
* For lists you should always prefer to use `Seq` - it is about 10x faster than `Lst`. The only reason you'd pick
`Lst` is if you needed to do inserts into the middle of the list: `Seq` doesn't allow this (it only allows prepending or
appending), as it would be a performance hit.
`Seq` is backed by an array, and so it has exceptional memory locality, `Lst` is an AVL tree to allow for efficient
insertion, but suffers from poorer memory locality.
* For 'dictionaries' or maps as we prefer to call them, then `HashMap` is the fastest implemention you'll find in .NET-land. It is
unsorted. If you need a sorted dictionary, use `Map`. `HashMap` uses the CHAMP data-structure, `Map` uses an AVL tree.
* The same goes for sets, prefer `HashSet` over `Set`, unless you need the set to be sorted.
You can construct the collection types using the constrctor functions in the `Prelude`:
HashMap hashSet = HashMap(("a", 1), ("b", 2), ("c", 3));
HashSet hashMap = HashSet(1, 2, 3);
Map hashSet = Map(("a", 1), ("b", 2), ("c", 3));
Set hashMap = Set(1, 2, 3);
Seq list = Seq(1, 2, 3);
Lst list = List(1, 2, 3);