Source file VisitorsList.ml

open List

(* [last xs] returns the last element of the nonempty list [xs]. *)

let rec last1 x xs =
  match xs with
  | [] ->
      x
  | x :: xs ->
      last1 x xs

let last xs =
  match xs with
  | [] ->
      assert false
  | x :: xs ->
      last1 x xs

(* [interval i j] constructs a list representation of the semi-open interval
   [i..j). *)

let rec interval i j : int list =
  if i < j then
    i :: interval (i + 1) j
  else
    []

(* [init i j f] constructs a list of the values [f i] up to [f (j - 1)]. *)

let init i j (f : int -> 'a) : 'a list =
  map f (interval i j)

(* [is_matrix m n xss] checks that [xss] is an [m]-by-[n] matrix, represented
   as a list of lists. *)

let is_matrix m n (xss : _ list list) =
  length xss = m && for_all (fun xs -> length xs = n) xss

(* [transpose n xss] transposes a matrix, represented as a list of lists.
   The parameter [n] is the width of the matrix, and is really useful only
   in the case where the matrix has zero height, in which case [transpose]
   constructs a matrix of height [n] and zero width. *)

let transpose (n : int) (xss : 'a list list) : 'a list list =
  let m = length xss in
  assert (is_matrix m n xss);
  (* Convert [xss] to an array, for speed. *)
  let xss : 'a array array =
    Array.(map of_list (of_list xss))
  in
  (* We have an [m]-by-[n] matrix, and construct an [n]-by-[m] matrix. *)
  init 0 n (fun j ->
    init 0 m (fun i ->
      xss.(i).(j)
    )
  )

(* [hextend xs n f] extends the vertical vector [xs] to a matrix of width [n].
   A vector element [x] is turned into [f j x] in the [j]-th row. *)

let hextend (xs : 'a list) (n : int) (f : int -> 'a -> 'a) : 'a list list =
  map (fun x -> init 0 n (fun j -> f j x)) xs

(* [uniq cmp xs] assumes that the list [xs] is sorted according to the
   ordering [cmp] and returns the list [xs] deprived of any duplicate
   elements. *)

let rec uniq1 cmp x ys =
  match ys with
  | [] ->
      []
  | y :: ys ->
      if cmp x y = 0 then
        uniq1 Stdlib.compare x ys
      else
        y :: uniq1 cmp y ys

let uniq cmp xs =
  match xs with
  | [] ->
      []
  | x :: xs ->
      x :: uniq1 cmp x xs

(* [weed cmp xs] returns the list [xs] deprived of any duplicate elements. *)

let weed cmp xs =
  uniq cmp (List.sort cmp xs)

(* [fold_right1] is like [fold_right], but uses the last element of the list
   (if the list is nonempty) as the initial accumulator, saving one call to
   the binary operation [f]. This is equivalent to [fold_right] if [accu] is
   a right unit for [f]. *)

let fold_right1 f xs accu =
  match List.rev xs with
  | [] ->
      accu
  | x :: xs ->
      let xs = List.rev xs in
      (* We have decomposed [xs] as [xs] followed with [x]. We can now
         ignore [accu] and use [x] as the initial accumulator in our
         right-to-left sweep of the list. *)
      List.fold_right f xs x

(* [fold_left1] is like [fold_left], but uses the first element of the list
   (if the list is nonempty) as the initial accumulator, saving one call to
   the binary operation [f]. This is equivalent to [fold_left] if [accu] is
   a left unit for [f]. *)

let fold_left1 f accu xs =
  match xs with
  | [] ->
      accu
  | x :: xs ->
      (* We can ignore [accu] and use [x] as the initial accumulator in
         our left-to-right sweep of the list. *)
      List.fold_left f x xs

(* [filter2 f xs ys] returns the list of elements [y] in [ys] such that
   the corresponding element [x] in [xs] satisfies [f]. *)

let filter2 f xs ys =
  assert (length xs = length ys);
  map snd (filter (fun (x, _y) -> f x) (combine xs ys))