Efficiently checking if Map/Set is singleton?

Learning
, ,
1

Map/Set provide O(1) is_empty functions, but they don’t provide is_singleton functions. Concretely, I would like O(1) functions

Set.(is_singleton : 'val t -> 'val option)
Map.(is_singlelton : ('key,'val) t -> ('key * 'val) option)

Maybe the length functions are guaranteed to be O(1), and so I can achieve this simply by using is_length followed by to_list?

2

Depends on whether you’re using the Core Map or the stdlib Map. Core’s (Base’s) Map and Set return length in O(1), but the stdlib’s are O(n).

┌──────────────┬─────────────┬────────────┐
│ Name         │    Time/Run │ Percentage │
├──────────────┼─────────────┼────────────┤
│ stdlib:1     │      9.56ns │      0.02% │
│ stdlib:10    │     51.94ns │      0.10% │
│ stdlib:100   │    505.01ns │      0.92% │
│ stdlib:1000  │  4_899.77ns │      8.97% │
│ stdlib:10000 │ 54_595.93ns │    100.00% │
│ core:1       │      3.56ns │            │
│ core:10      │      3.56ns │            │
│ core:100     │      3.67ns │            │
│ core:1000    │      3.52ns │            │
│ core:10000   │      4.01ns │            │
└──────────────┴─────────────┴────────────┘

See this gist for the benchmark. (compile with dune/jbuilder or corebuild -pkg core_bench).

2 Likes
3

I usually use Base/Core, so that will work for me.
Seems like an embarrassing flaw in the standard library, though…

4

For the stdlib you could always do something ugly like this:

module S = Set.Make (String)

exception Done

let sole_element set =
  let cell = ref None in
  begin try
      S.iter (fun x ->
          match !cell with
          | None -> cell := Some x
          | Some _ -> cell := None; raise Done)
        set;
    with Done -> ()
  end;
  !cell
1 Like
5

Here is another way to test for a singleton set in the standard lib:

module S = Set.Make(String)

let is_singleton s =
  try S.min_elt s = S.max_elt s with Not_found -> false

This doesn’t generalize nicely to arbitrary cardinality tests.

6

One more using stdlib:

module String_set = struct
  include Set.Make (String)

  let is_singleton s =
    match choose_opt s with
    | None -> false
    | Some e -> equal s (singleton e)
end
7 
(* O(log n), a bit less polymorphic than necessary as it depends on equality of keys.
    corrected: I thought it was O(1), gsg pointed out it is logarithmic. My bad! *)
let is_singleton s =
  match split (choose s) s with
  | exception Not_found -> false (* empty *)
  | (l, _, r) -> is_empty l && is_empty r

(* polymorphic (it depends only on the structure of the container, not on elements),
   but O(log n) as iter/fold has to traverse the left-most branch before starting to iterate *)
let is_singleton s =
  match fold (fun elt count -> if count > 0 then raise Exit else count + 1) s 0 with
  | 1 -> true
  | _ -> false
  | exception Exit -> false

Should work on Set and Map (slightly adapting the fold function, doesn’t depend on elements of the map).

8

Another variation, using exists/for_all functions, which dontt do in order traversal, thus are O(1) (in this case):

let is_singleton s =
  not (is_empty s) && 
  let count = ref 0 in for_all (fun _ -> incr count; !count = 1) s
1 Like
9

O(1) for a reasonable implementation

choose is O(log n), though? That’s why it can guarantee equal elements for equal sets.

O(log n) as iter/fold has to traverse the left-most branch

Nuts.

1 Like
10

Arrgghh, you are right. choose is indeed O(log n) (would work with sets with a unique structure, such as patricia :P).
It happens to be min_elt in current implementation.

11

Seems as if the exists approach is the least bad. I suppose that occasionally having to write this kind of ugly code is the downside of abstract data types with minimalist interfaces.

12

Checking equality can be expensive in general, so I would like to avoid that.