This library provides a simple yet powerful way to write incremental functional computations that can be connected to imperative sources on both input and output.

Examples include:

• adaptive views in data-driven user interfaces
• adaptive computations in incremental data-driven scientific and financial models

`FSharp.Data.Adaptive` focuses on 'adaptive values' and 'adaptive data' rather than reactive events.

Adaptive values (`aval`) are similar to cells in Excel spreadsheets. Consider a physics simulation such as the time taken for a ball to fall from a particular height. If you like think of `sqrt (2.0 * height / gravity)` as a formula in an Excel spreadsheet, where `height` and `gravity` are the names of other cells. The functional and adaptive forms are:

``````let timeToFloor height gravity =
sqrt (2.0 * height / gravity)

AVal.map2 (fun h g -> sqrt (2.0 * h / g)) height gravity
``````

The `AVal.map2` is glue to connect this formula to other cells, producing a new cell.

Now let's define the cells `height` and `gravity`, make them changeable (`cval`), that is, user-editable. Initially the inputs contain the values on Earth:

``````let height  = cval 10.0
let gravity = cval 9.81
let dropTime = adaptiveTimeToFloor height gravity
``````

We can now observe the result of the output 'cell':

``````printfn "%.3fs" (AVal.force dropTime) // => 1.428s
``````

The user (or something else in the system) can now adjusts the changeable inputs to the values for the moon:

``````transact (fun () -> gravity.Value <- 1.62)
printfn "%.3fs" (AVal.force dropTime) // => 3.514s
``````

And now adjust to a height of 2000m on Jupiter:

``````transact (fun () ->
gravity.Value <- 24.79
height.Value <- 2000.0
)
printfn "%.3fs" (AVal.force dropTime) // => 12.703s
``````

This example feels a lot like an Excel calculation, in which dependent cells get updated whenever changeable inputs change. Some important differences are

1. All 'cells' are adaptive values
2. 'Cells' are first-class values
3. Changeable 'cells' are distinguished from computed
4. In the above, each 'cell' gets named explcitly in program code, rather than using implicit naming on a sheet
5. Some glue like `AVal.map2` is needed to connect cells

6. User code is responsible for making changes using `transact`

7. Re-calc happens on-demand as outputs are observed

Some API elements you have seen so far are:

• `aval` Adaptive Value. Adaptive cell whose value purely depends on other adaptive cells.
• `map` `map2` `map3` Create a new `aval` whose value depends on the one (two, three) input `aval`(s).
• `cval` Changeable Value. Adaptive cell whose value can be manually set. A `cval` is also an `aval`.
• `transact` Set a `cval`'s value within this scope.
• `force` Read an `aval`'s value.

Cells in an Excel spreadsheet can only contain an individual value. What if a 'cell' could be an entire set, array, list or table? And what if the user makes incremental modifications to such a cell, adding a row, deleting a selection of elements and so on? Would the rest of the spreadsheet adjust to this incremental change in the collection, or would dependent cells recalculate over the entire new collection?

As seen in the examples above `aval<'T>` and `cval<'T>` are containers for single values that may change adaptively. A natural way of handling collections of values would be `aval<Set<'T>>`. However, this forces recalculation by iterating the entire collection. For example, a mapping function on the set would look like this:

``````let map (mapping: 'T1 -> 'T2) (set : aval<Set<'T1>>) =
set |> AVal.map (Set.map mapping)
``````

Note the use of `Set.map` means that `mapping` will be executed for all elements of the set even if just a single element changes.

• `cset`/`ChangeableHashSet` Adaptive modifiable input set.
• `aset`/`AdaptiveHashSet` Adaptive set. Content depends on other adaptive cells.

Adaptive sets work on deltas instead of values. Here's an example illustrating `aset`s:

``````let inputSet = cset [1;2;3]
let dependentSet =
inputSet |> ASet.map (fun v -> printf "map %d, " v; v * 2)

printfn "%A" (AVal.force dependentSet.Content) // => map 1, map 2, map 3, HashSet [2; 4; 6]
``````

We create an `aset` and specify a mapping function on the elements. The mapping is evaluated for each element individually, as illustrated by the three "map" prints.

Let's add an element to the set.

``````transact (fun () -> inputSet.Add 0)
printfn "%A" (AVal.force dependentSet.Content) // => map 0, HashSet [0; 2; 4; 6]
``````

The mapping function is evaluated only once, for the newly added element! `aset` is an incremental data structure on the level of its contained elements.

``````transact (fun () -> inputSet.Remove 2)
printfn "%A" (AVal.force dependentSet.Content) // => HashSet [0; 2; 6]
``````

There is no "map" print - the removal did not trigger an evaluation of the mapping function!

In addition to the unordered set, we also have implementations of the ordered list, called `alist`, and the key-value map, called `amap`.

## Dynamic computation graphs and dynamic dependencies

An Excel spreadsheet has a static structure of cells with static dependencies. The API becomes more interesting when dynamic dependencies come into play. That is, adaptive values can dynamically decide whether or not to depend on something based on their content.

As an example, let's extend our computation by calculating the height of our ball at a certain point in time.

``````// simple utility calculating the height
let calcHeight (t : float) (h0 : float) (g : float) =
printf "height after %.3fs: " t
h0 - 0.5*g*t*t

let time = cval 0.5

let currentHeight = AVal.map3 calcHeight time height gravity
printfn "%.3fm" (AVal.force currentHeight) // => height after 0.500s: 1996.901m
printfn "%.3fm" (AVal.force currentHeight) // => 1996.901m
printfn "%.3fm" (AVal.force currentHeight) // => 1996.901m
``````

Note that we snuck a little "height after" print into the utility calculation. This is for illustrative purposes: observe how the print occurs only when `currentHeight` needs to re-calculate its value. It happens only at initial calculation or when one of its inputs changes!

But, oh no! Someone could enter an invalid time (let's say -100s)!

``````transact (fun () -> time.Value <- -100.0)
printfn "%.3fm" (AVal.force currentHeight) // => height after -100.000s: -121950.000m
``````

We'd like to prevent that!

Let's rewrite the code using a dynamic dependency.

``````let currentHeightSafe =
let! t = time
if t <= 0.0 then
// whenever the time is negative the ball will just report its initial height.
return! height :> aval<_>
else
// when the time is positive we use our utility to calculate the height at the current time.
return! AVal.map2 (calcHeight t) height gravity
}

printfn "%.3fm" (AVal.force currentHeightSafe) // => 2000.000m
``````

The content of `currentHeightSafe` is now 2000.0, since our time is still negative and we decide to return the content of `height`. Observe the fact that there is no "height after" print! There's no need to run our utility calculation at this time.

What happens if we change the gravity back to earth?

``````transact (fun () -> gravity.Value <- 9.81)
printfn "%.3fm" (AVal.force currentHeightSafe) // => 2000.000m
``````

Nothing changed, since `currentHeightSafe` currently does not depend on `gravity`. There is no "height after" print!

Okay, set the height to 10m again.

``````transact (fun () -> height.Value <- 10.0)
printfn "%.3fm" (AVal.force currentHeightSafe) // => 10.0m
``````

Our value of `currentHeightSafe` got updated to represent the new value of `height`. There is still no "height after" print!

Finally, let's set the time to a positive value again.

``````transact (fun () -> time.Value <- 1.42785)
printfn "%.3fm" (AVal.force currentHeightSafe) // height after 1.428s: 0.000m
``````

And there's our "height after" print. We decided to depend on the utility calculation again.

• `bind` Create a dynamic dependency. The resulting `aval` may dynamically decide on which `aval`s to depend.
• Dependency graph. A chain of dependent `aval`s.
• Dynamic dependency graph. A dependency graph that includes dynamic dependencies.

This simple example demonstrates the capacity of `aval`s to express dynamic dependency graphs. In this example, the system knew exactly that `currentHeightSafe` didn't depend on `gravity`/`height` as long as `time` was negative. As soon as `time` became positive, the system precisely maintained the resulting structure of the dependencies.

The advantage is immediately clear: If the dependencies contained heavyweight computations, the system ensures only the minimal amount of effort is expended for updates whenever a result is requested. Traditional reactive programming libraries typically struggle to model dynamic dependency graphs, but adaptive embraces them as its core motivation.

# Implementation Details

`cval<'T>` and `cset<'T>` also implement the unifying type `aval<'T>` and `aset<'T>` respectively. The changeable values can be used in places where adaptive value are expected (as seen in the example above). This helps the API to look nice.

The system distinguishes between two different kinds of objects:

Changeable input values, which are prefixed with the letter c (e.g. `cval<'T>`, `cset<'T>`), and can imperatively be modified by user-code.

And Dependent values, which are prefixed with the letter a (e.g. `aval<'T>`, `aset<'T>`). These cannot directly be modified but instead depend on other adaptive values.

Internally, there is a third kind of adaptive value: The constant value, which can never be changed. In our system these are not expressed on the type-level, but instead expose a property `IsConstant`. All combinators correctly propagate constants in the dependency graph (when possible) and therefore:

``````let shouldBeConstant = AVal.constant 5 |> AVal.map (fun v -> v * 10)
printfn "%A" (AVal.force shouldBeConstant)  // ==> 50
printfn "%A" shouldBeConstant.IsConstant // => true
``````

Whenever values are not constant, combinators like `AVal.map` internally build a dependency graph that keeps track of dependencies between cells. This dependency graph is used to find out what needs to be re-computed whenever changes are fed into the system.

Supplying changes to changeable cells can be done using `transact : (unit -> 'T) -> 'T`. The function makes the dependency graph consistent according to the nature and scope of the changes.

## Evaluation strategy, avoidance of re-execution

Our system uses a push-pull evaluation strategy, meaning that evaluation will (by default) be lazy. This is achieved via eagerly marking all affected values as outOfDate, and lazily making them upToDate whenever they're evaluated. We opted for lazy evaluation since it causes unneeded parts of the dependency graph to impose virtually no runtime overhead. Lazy evaluation also allows us to support (limited) concurrency in the system.

On the downside, the marking process (performed by `transact`) needs to mark all potentially affected values as outOfDate, even if their resulting value has not changed. However, we did our best to avoid re-execution of unchanged functions. Here's an example illustrating our system's behaviour in such a circumstance:

``````let someInput = cval 10
let someOutput =
someInput
|> AVal.map (fun v -> printf "%d %% 2 => " v; v % 2)
|> AVal.map (fun v -> printf "%d * 10 => " v; v * 10)

printf "%A: " someOutput.OutOfDate; printfn "%A" (AVal.force someOutput) // => true: 10 % 2 => 0 * 10 => 0
transact (fun () -> someInput.Value <- 12)
printf "%A: " someOutput.OutOfDate; printfn "%A" (AVal.force someOutput) // => true: 12 % 2 => 0
``````

Note that the `v * 10` function doesn't get executed after the change, even though its result has been marked outOfDate. The system understood that the output wouldn't have changed either way.

Multiple items
namespace FSharp

--------------------
namespace Microsoft.FSharp
Multiple items
namespace FSharp.Data

--------------------
namespace Microsoft.FSharp.Data
val timeToFloor: height: float -> gravity: float -> float
val height: float
val gravity: float
val sqrt: value: 'T -> 'U (requires member Sqrt)
val adaptiveTimeToFloor: height: aval<float> -> gravity: aval<float> -> aval<float>
val height: aval<float>
val gravity: aval<float>
Multiple items

--------------------
<summary> Operators related to the aval&lt;_&gt; type </summary>
val map2: mapping: ('T1 -> 'T2 -> 'T3) -> value1: aval<'T1> -> value2: aval<'T2> -> aval<'T3>
<summary> Returns a new adaptive value that adaptively applies the mapping function to the given adaptive inputs. </summary>
val h: float
val g: float
val height: cval<float>
type cval<'T> = ChangeableValue<'T>
<summary> Represents an adaptive value that can be changed by application code and Used in dependency-aware computations. </summary>
val gravity: cval<float>
val dropTime: aval<float>
val printfn: format: Printf.TextWriterFormat<'T> -> 'T
val force: value: aval<'T> -> 'T
<summary> Evaluates the given adaptive value and returns its current value. This should not be used inside the adaptive evaluation of other AdaptiveObjects since it does not track dependencies. </summary>
val transact: action: (unit -> 'T) -> 'T
<summary> Executes a function "inside" a newly created transaction and commits the transaction. </summary>
property ChangeableValue.Value: float with get, set
<summary> Gets or sets the current value. Setting the value requires a Transaction to be active using `transact`. </summary>
val map: mapping: ('T1 -> 'T2) -> set: aval<Set<'T1>> -> aval<Set<'T2>> (requires comparison and comparison)
val mapping: ('T1 -> 'T2) (requires comparison and comparison)
val set: aval<Set<'T1>> (requires comparison)
Multiple items
val aval: AValBuilder
<summary> ComputationExpression builder for aval. </summary>

--------------------
<summary> An abbreviation for AdaptiveValue </summary>
Multiple items
union case ElementOperation.Set: 'T -> ElementOperation<'T>
<summary> Set the associated key to a specific value. </summary>

--------------------
module Set from Microsoft.FSharp.Collections

--------------------
type Set<'T (requires comparison)> = interface IReadOnlyCollection<'T> interface IStructuralEquatable interface IComparable interface IEnumerable interface IEnumerable<'T> interface ICollection<'T> new: elements: 'T seq -> Set<'T> member Add: value: 'T -> Set<'T> member Contains: value: 'T -> bool override Equals: obj -> bool ...

--------------------
new: elements: 'T seq -> Set<'T>
val map: mapping: ('T1 -> 'T2) -> value: aval<'T1> -> aval<'T2>
<summary> Returns a new adaptive value that adaptively applies the mapping function to the given adaptive inputs. </summary>
val map: mapping: ('T -> 'U) -> set: Set<'T> -> Set<'U> (requires comparison and comparison)
val inputSet: cset<int>
type cset<'T> = ChangeableHashSet<'T>
<summary> An abbreviation for ChangeableHashSet </summary>
val dependentSet: aset<int>
Multiple items
<summary> Functional operators for aset&lt;_&gt; </summary>

--------------------
<summary> Functional operators for aset&lt;_&gt; </summary>
val map: mapping: ('A -> 'B) -> set: aset<'A> -> aset<'B>
<summary> Adaptively maps over the given set. </summary>
val v: int
val printf: format: Printf.TextWriterFormat<'T> -> 'T
<summary> The current content of the set as aval. </summary>
member ChangeableHashSet.Add: value: 'T -> bool
member ChangeableHashSet.Remove: value: 'T -> bool
val calcHeight: t: float -> h0: float -> g: float -> float
val t: float
Multiple items
val float: value: 'T -> float (requires member op_Explicit)

--------------------
type float = System.Double

--------------------
type float<'Measure> = float
val h0: float
val time: cval<float>
val currentHeight: aval<float>
val map3: mapping: ('T1 -> 'T2 -> 'T3 -> 'T4) -> value1: aval<'T1> -> value2: aval<'T2> -> value3: aval<'T3> -> aval<'T4>
<summary> Returns a new adaptive value that adaptively applies the mapping function to the given adaptive inputs. </summary>
val currentHeightSafe: aval<float>
<summary> ComputationExpression builder for aval. </summary>
val shouldBeConstant: aval<int>
val constant: value: 'T -> aval<'T>
<summary> Creates a constant adaptive value always holding the given value. The system internally propagates constants. </summary>