Module Shared_ast.BoundList

Bound lists are non-empty linked lists where each element is a binder onto the next. They are useful for ordered program definitions, like nested let-ins.

let a = e1 in e2 is thus represented as Cons (e1, {a. Last e2}).

The following provides a few utility functions for their traversal and manipulation. In particular, map functions take care of unbinding, then properly rebinding the variables.

type ('e, 'elt, 'last) t =
  1. | Last of 'last
  2. | Cons of 'elt * ('e, ('e, 'elt, 'last) t) Shared_ast__.Definitions.binder
val to_seq : (((_, _, _) Shared_ast__.Definitions.base_gexpr, _ Shared_ast__.Definitions.mark) Catala_utils.Mark.ed as 'e, 'elt, _) t -> ('e Var.t * 'elt) Stdlib.Seq.t

Note that the boundlist terminator is ignored in the resulting sequence

val of_list : ('e Var.t * 'elt Bindlib.box) list -> last:'last Bindlib.box -> ('e, 'elt, 'last) t Bindlib.box
val last : (_, _, 'a) t -> 'a
val iter : f:('e Var.t -> 'elt -> unit) -> ('e, 'elt, 'last) t -> 'last
val find : f:('elt -> 'a option) -> (_, 'elt, _) t -> 'a
val fold_left : f:('acc -> 'elt -> 'e Var.t -> 'acc) -> init:'acc -> ('e, 'elt, 'last) t -> 'acc * 'last
val fold_left2 : f:('acc -> 'elt1 -> 'elt2 -> 'e Var.t -> 'acc) -> init:'acc -> ('e, 'elt1, 'last1) t -> ('e, 'elt2, 'last2) t -> 'acc * ('last1 * 'last2)
val fold_right : f:('elt -> 'e Var.t -> 'acc -> 'acc) -> init:('last -> 'acc) -> ('e, 'elt, 'last) t -> 'acc
val fold_lr : top:'dacc -> down:('e Var.t -> 'elt -> 'dacc -> 'dacc) -> bottom:('last -> 'dacc -> 'uacc) -> up:('e Var.t -> 'elt -> 'uacc -> 'uacc) -> ('e, 'elt, 'last) t -> 'uacc

Bi-directional fold: down accumulates downwards, starting from top; upon reaching last, bottom is called; then up accumulates on the way back up

val map : f:('e1 Var.t -> 'elt1 -> 'e2 Var.t * 'elt2 Bindlib.box) -> last:('last1 -> 'last2 Bindlib.box) -> ('e1, 'elt1, 'last1) t -> ('e2, 'elt2, 'last2) t Bindlib.box
val map_last : f:('e1 Var.t -> 'elt1 -> 'e2 Var.t * 'elt2 Bindlib.box) -> last:('last1 -> ('e2, 'elt2, 'last2) t Bindlib.box) -> ('e1, 'elt1, 'last1) t -> ('e2, 'elt2, 'last2) t Bindlib.box

A more expressive version of map that allows extending the tail (e.g. to append new elements)

val fold_map : f:('ctx -> 'e1 Var.t -> 'elt1 -> 'ctx * 'e2 Var.t * 'elt2 Bindlib.box) -> last:('ctx -> 'last1 -> 'ret * 'last2 Bindlib.box) -> init:'ctx -> ('e1, 'elt1, 'last1) t -> 'ret * ('e2, 'elt2, 'last2) t Bindlib.box
val equal : f:('elt -> 'elt -> bool) -> last:('last -> 'last -> bool) -> (('e, 'elt, 'last) t as 'l) -> 'l -> bool
val compare : f:('elt -> 'elt -> int) -> last:('last -> 'last -> int) -> (('e, 'elt, 'last) t as 'l) -> 'l -> int