DOCSEARCHbyAlgolia
Submit Docs

OCaml-containers

repository·main·Indexed 19 days ago

https://github.com/c-cube/ocaml-containers

A modular extension of the OCaml standard library providing advanced data structures, combinators, and iterators. It includes the core 'containers' library with CC-prefixed modules, 'containers-data' for specialized structures like functional double-ended queues, and sub-libraries for unix utilities, bencode, CBOR, and SCC algorithms. Key components include CCVector for resizable arrays, CCHeap for priority queues, CCIO for safe resource management, and CCParse for string parser combinators.

Tokens
3.8K
Snippets
11
Records
16
Agent score
18%

What's inside OCaml-containers

  1. Understand the Containers module structure

    main

    OCaml-containers is organized into several parts:

    • containers (core): The main library (packaged as containers in ocamlfind). Modules are prefixed with CC (e.g., CCList) to avoid namespace collisions. It also provides a Containers module intended to be opened as a drop-in replacement for the standard library.
    • containers-data: A separate package containing additional data structures that do not have equivalents in the OCaml standard library.
    • Sub-libraries:
      • containers.unix: Utilities for the unix library (e.g., safe sub-process spawning).
      • containers.bencode: Bencode codec for Bittorrent-style serialization.
      • containers.cbor: CBOR binary serialization codec.
      • containers.scc: Functorized Strongly Connected Component algorithm.
    • Standalone libraries: Some components like iter (formerly sequence) and gen have been moved to their own repositories and are available on opam.

  2. Use CCHeap for priority queues

    main

    CCHeap provides a functional priority queue (implemented as leftist heaps). It is functorized over a module that defines the type t and a comparison function leq : t -> t -> bool.

    • Creation: Use CCHeap.Make(module_with_leq) to create the heap module.
    • Operations: CCHeap.take removes the highest priority element and returns it along with a new heap. Because it is a functional data structure, the original heap remains unchanged.
    • Conversion: You can convert a CCVector to a CCHeap using CCVector.to_iter |> IntHeap.of_iter.
    module IntHeap = CCHeap.Make(struct type t = int let leq = (<=) end);;
# let h = v2 |> CCVector.to_iter |> IntHeap.of_iter ;;
# let h', x = IntHeap.take_exn h;; (* returns new heap and the element *)

  3. Use CCVector for resizable arrays

    main

    CCVector is a resizable array that supports both immutable (CCVector.ro) and mutable (CCVector.rw) modes.

    • Creation: Use CCVector.create for an empty mutable vector, or CCVector.init to initialize with a specific size and function.
    • Range Syntax: Use the infix operator -- within the CCVector module to create a range (e.g., CCVector.(1 -- 10)).
    • Mutability: A vector can transition from immutable to mutable via operations like CCVector.push.
    • Functional API: Even when using mutable vectors, you can use functional combinators like CCVector.map, CCVector.filter, and CCVector.rev to produce new read-only vectors.
    # let v = CCVector.(1 -- 10);;
# CCVector.push v 42;; (* v is now mutable *) 
# let v2 = v |> CCVector.map (fun x -> x + 1) |> CCVector.filter (fun x -> x mod 2 = 0) |> CCVector.rev ;;

  4. Understand monomorphic operators in Containers

    main

    By default, when using open Containers, operators like equality (=) and comparison (<) are monomorphic rather than polymorphic.

    Why? Polymorphic comparison can lead to bugs when structural comparison differs from semantic comparison (e.g., comparing Maps or Hashtables). Monomorphic operators force you to be explicit, preventing subtle bugs where identical semantic values are seen as different due to their internal structure.

    How to use them:

    • To use polymorphic operators: Access them via the Stdlib module (e.g., Stdlib.(=), Stdlib.max).
    • Migration tip: If you are migrating a module, you can open Stdlib immediately after open Containers to restore default behavior.
    • Best Practice: For public types, export explicit equal, compare, and hash functions. This ensures compatibility with Hashtbl.Make and Map.Make and makes your module future-proof.

  5. Introduction to OCaml-containers basics

    main

    OCaml-containers provides enhanced versions of standard library data structures and new specialized types. To use the library, ensure it is installed and loaded via #require "containers";; in your OCaml environment.

    List Helpers

    Use CCList for advanced list manipulations. For example, you can use CCList.filter_map to transform and filter a list in one pass, or CCList.take to limit the number of elements.

    Map Usage

    Maps can be created using CCMap.Make(Module) where Module provides the necessary comparison logic (e.g., CCInt).

    Iterators

    The library uses iter types ('a iter = (unit -> 'a) -> unit) for high-performance iteration. You can convert lists to iterators using CCList.to_iter and create maps from iterators using IntMap.of_iter (or similar map modules).

    # #require "containers";;
# Format.set_margin 50;;

# open CCList.Infix;;
# let l = 1 -- 100;;
# l |> CCList.filter_map (fun x -> if x mod 3 = 0 then Some (float x) else None) |> CCList.take 5;;
# - : float list = [3.; 6.; 9.; 12.; 15.]

  6. Migrate from Containers 2.0 to 3.0

    main

    If you are upgrading from version 2.0 to 3.0, note the following breaking changes:

    1. Package Changes:
      • containers.sexp (CCSexp) is now part of the main containers package.
      • containers.data is now the separate containers-data package.
      • containers.iter has been deleted.
    2. Iterator Changes: Functions like CCVector.of_seq now use the standard Seq.t type. Old iteration-based functions are now named of_iter, to_iter, etc.
    3. Removals: Array_slice and String.Sub have been removed.
    4. Renamed Functions:
      • CCVector.shrink $\rightarrow$ CCVector.truncate
      • CCVector.remove $\rightarrow$ CCVector.remove_unordered (use CCVector.remove_and_shift for the previous behavior).
      • CCPair.map_fst and map_snd now return a new tuple with the modified element.
    5. Pretty-printers: Collection printers now take a unit printer (Format.formatter -> unit -> unit) instead of a string for separators/start/stop arguments.

  8. Debug Containers values with `ocamldebug`

    main

    To print values defined in containers within the bytecode debugger, you must load the appropriate bytecode archives and install the printers.

    1. Start your session: ocamldebug your_program.bc.
    2. Load the printers:
    # #load_printer containers_monomorphic.cma;;
# #load_printer containers.cma;;
    1. Install a specific printer (e.g., for Containers.Int):
    # #install_printer Containers.Int.pp;;

    Note on Combinators: Printer combinators (like List.pp) do not work directly in ocamldebug. To use them, define a module containing the combined printer and load that module instead:

    module M = struct
  let pp_int_list = Containers.(List.pp Int.pp)
end;;
# #load_printer m.cmo
# #install_printer M.pp_int_list
    # #load_printer containers_monomorphic.cma;;
# #load_printer containers.cma;;
# #install_printer Containers.Int.pp;;

  9. Use containers-data for advanced structures

    main

    For more specialized data structures like purely functional double-ended queues, use the containers-data library. You must link it or use #require "containers-data";; to access it.

    Example using CCFQueue:

    • CCFQueue.of_list: Create a queue from a list.
    • CCFQueue.cons: Add elements to the front.
    • CCFQueue.take_front: Remove the front element (returns (element * queue) option).
    • CCFQueue.take_back_l: Remove elements from the back (returns (new_queue * removed_elements_list)).
    # #require "containers-data";;
# let q = CCFQueue.of_list [2;3;4];;
# let q2 = q |> CCFQueue.cons 1 |> CCFQueue.cons 0;;
# let (q_new, x) = CCFQueue.take_front q2 |> Option.get;;

  10. Use OCaml-containers in a toplevel

    main

    To use the library in an OCaml toplevel with topfind, require the containers package. You can access modules via their CC prefix (e.g., CCList) or by using open Containers to bring enhanced versions of standard modules into scope.

    # #use "topfind";;
...
# #require "containers";;
# #require "containers-data";;
CCList.flat_map;;
- : ('a -> 'b list) -> 'a list -> 'b list = <fun>
# open Containers (* optional *);;
# List.flat_map ;;
- : ('a -> 'b list) -> 'a list -> 'b list = <fun>

  11. Implement a recursive expression parser with `CCParse`

    main

    Using CCParse, you can implement complex recursive descent parsers (like mathematical expressions) by combining basic combinators and using P.fix to handle recursion.

    Example implementation of an arithmetic expression parser:

    ```ocaml
open CCParse.Infix
module P = CCParse

let parens p = P.try_ (P.char '(') *> p <* P.char ')'
let add = P.char '+' *> P.return (+)
let sub = P.char '-' *> P.return (-)
let mul = P.char '*' *> P.return (*)
let div = P.char '/' *> P.return (/)
let integer =
  P.chars1_if (function '0'..'9'->true|_->false) >|= int_of_string

let chainl1 e op =
  P.fix (fun r ->
    e >>= fun x -> P.try_ (op <*> P.return x <*> r) <|> P.return x)

let expr : int P.t =
  P.fix (fun expr ->
    let factor = parens expr <|> integer in
    let term = chainl1 factor (mul <|> div) in
    chainl1 term (add <|> sub))

(* Usage *) 
P.parse_string expr "4*1+2";; (* Result: Ok 6 *) 
P.parse_string expr "4*(1+2)";; (* Result: Ok 12 *)```

  12. Use `CCParse` for string parser combinators

    main

    The CCParse module provides basic parser combinators for strings. It requires explicit backtracking using try_ and supports explicit memoization via memo and fix_memo.

    When building parsers, you can use CCParse.Infix for a more readable syntax. Common patterns include:

    • try_: Enables backtracking.
    • fix: Used for recursive parsers.
    • *>, <*, >>=, <|>: Standard combinator operators for sequencing, discarding results, binding, and choice.
    • parse_string: The primary function to execute a parser against a string, returning a Result.Ok or error.
    open CCParse.Infix
module P = CCParse

(* Example: A simple integer parser *) 
let integer =
  P.chars1_if (function '0'..'9'->true|_->false) >|= int_of_string

(* Execute the parser *) 
P.parse_string integer "123";;