Reactive Programming with Diff and Patch

What is Incremental?

  • Implementation of self-adjusting computations, Acar et. al.
  • Embed your computation in a (dynamic) dependency graph
  • Three parts: variables, incrementals and observers

The Incremental API

module Incr : sig
  type 'a t

  val return : 'a -> 'a t
  val map    : 'a t -> ('a -> 'b) -> 'b t
  val map2   : 'a t -> 'b t -> ('a -> 'b -> 'c) -> 'c t
  val bind   : 'a t -> ('a -> 'b t) -> 'b t
end

The API, continued

module Var : sig
  type 'a t
  val create : 'a -> 'a t
  val set    : 'a t -> 'a -> unit
  val watch  : 'a t -> 'a Incr.t
end
module Obs : sig
  type 'a t
  val create : 'a Incr.t -> 'a t
  val value  : 'a t -> 'a
end
val stabilize : unit -> unit

Two ifs

let map_if c t e =
  let%map c = c and t = t and e = e in
  if c then t else e
let bind_if c t e =
  let%bind c = c in
  if c then t else e

Dynamic graphs

val sum : float Incr.t list -> float Incr.t
let dynamic_sum
    (values_by_id : float Incr.t Map.M(Id).t)
    (ids : Id.t list Incr.t)
  =
  let%bind ids = ids in
  let incrs =
    List.map ids (fun id -> Map.find_exn values_by_id id)
  in
  sum incrs

Incremental in practice

  • Well designed for a shattered world
  • Bind is dynamic, but limited
  • Hard to integrate with ordinary FP datastructures

Mapping over incremental maps

val map
  :  ('k, 'v1, 'cmp) Map.t Incr.t
  -> ('v1 -> 'v2)
  -> ('k, 'v2, 'cmp) Map.t Incr.t

Diffing maps

val symmetric_diff
  :  ('k, 'v, 'cmp) Map.t
  -> ('k, 'v, 'cmp) Map.t
  -> data_equal:('v -> 'v -> bool)
  -> ('k * [ `Left of 'v
           | `Right of 'v
           | `Unequal of 'v * 'v ]) Sequence.t

diff_map

val diff_map
  :  'a Incr.t
  -> (('a * 'b) option -> 'a -> 'b)
  -> 'b Incr.t
let diff_map i f =
  let old = ref None in
  let%map a = i in
  let b = f !old a in
  old := Some (a, b);
  b

Mapping over incremental maps

let map m f =
  diff_map m (fun old m ->
      match old with
      | None -> Map.map m ~f
      | Some (old_in, old_out) ->
        let diff =
          Map.symmetric_diff old_in m
            ~data_equal:phys_equal
        in
        Sequence.fold diff ~init:old_out
          ~f:(fun acc (key,change) ->
              match change with
              | `Left _ -> Map.remove acc key
              | `Unequal (_,data) | `Right data ->
                Map.set acc ~key ~data:(f data)))

Incrementally mapping over incremental maps

val map'
  :  ('k, 'v1, 'cmp) Map.t Incr.t
  -> ('v1 Incr.t -> 'v2 Incr.t)
  -> ('k, 'v2, 'cmp) Map.t Incr.t

Split and Join

val split
  :  ('k,'v       ,'cmp) Map.t Incr.t
  -> ('k,'v Incr.t,'cmp) Map.t Incr.t
val join
  :  ('k,'v Incr.t,'cmp) Map.t Incr.t
  -> ('k,'v       ,'cmp) Map.t Incr.t
 let map' m f =
   join (map (split m) f)

More Diff and Patch

  • Incr_map provides all this and more
  • Incr_select for focus management
  • Connecting to imperative APIs (e.g., virtual-dom)
  • Network protocols

General purpose functional glue!

Try it out!

http://opensource.janestreet.com/incremental