jonnifyfsharp

Dive C4.10.1

Deduplication by cost

Removing repeats is a one-liner. Which line you reach for is a choice about cost.

F# gives three answers to "drop the repeats", and they are not interchangeable. For a list you have in hand, List.distinct makes one pass. For items arriving over time, a Set answers membership as you go. And for a queue, the dedup set is a Map keyed by a branded id — which is exactly how the echo_fs bus refuses a job it has already admitted. Each result below was produced by dotnet fsi (9.0.303).

Admit jobs, watch the gate Module hub
C4.10.1 · part 1

List.distinct — the small case

List.distinct keeps the first occurrence of each element and drops the rest, leaving order intact. When the elements are records and you mean "unique by a field", List.distinctBy takes the key. Both are one line.

let jobs = ["a"; "b"; "a"; "c"; "b"; "a"]
List.distinct jobs
// val it: string list = ["a"; "b"; "c"]

type Event = { Id: string; At: int }
let evs = [ {Id="J1";At=1}; {Id="J2";At=2}; {Id="J1";At=3} ]
evs |> List.distinctBy (fun e -> e.Id) |> List.map (fun e -> e.Id)
// val it: string list = ["J1"; "J2"]

Efficiency. List.distinct builds a hash set as it walks the list — O(n) over the list, with one hash and one equality per element. It reads the whole list each call. That is the right tool for a single pass; it is the wrong shape when membership is checked again and again as items arrive. For that, hold the set.

C4.10.1 · part 2

The Set — dedup as you go

When repeats arrive over time, hold a Set of what you have seen and ask before you add. Set is the immutable balanced tree from C4.04: Set.contains and Set.add are O(log n), and Set.add shares structure with the old set rather than copying it — so threading the set through a fold costs no second copy of the data.

let seen = Set.ofList ["a"; "b"]
Set.contains "a" seen        // val it: bool = true
Set.add "c" seen |> Set.toList  // val it: string list = ["a"; "b"; "c"]

// fold a stream, keeping firsts, threading the seen-set
let dedupFold xs =
    xs
    |> List.fold (fun (seen, acc) x ->
        if Set.contains x seen then seen, acc
        else Set.add x seen, x :: acc) (Set.empty, [])
    |> snd |> List.rev

dedupFold ["a"; "b"; "a"; "c"; "a"]
// val it: string list = ["a"; "b"; "c"]

Elixir — MapSet, the same idea

# Elixir — a MapSet threaded through a reduce
seen = MapSet.new(["a", "b"])
MapSet.member?(seen, "a")   # => true
MapSet.put(seen, "c")        # => MapSet of "a", "b", "c"

F# — Set, by contrast

// F# — a typed Set; element type is checked at compile time
let seen = Set.ofList ["a"; "b"]   // Set<string>
Set.contains "a" seen              // val it: bool = true

The Elixir parity is E4.10: the same instinct — let the structure carry the work — applied to the same job. The difference F# adds is the element type, fixed at compile time, so a Set<string> cannot quietly take an int.

Admit jobs, watch the gate

This is the bus's dedup, run live. Each button admits a job by branded id into a Map keyed by that id. The gate is one check: if the id is already a key, the job is a duplicate and the row count does not move; otherwise it is admitted. The readout names the verdict — Admission.Enqueued or Admission.Duplicate — and the running row count.

enqueue id payload · the ContainsKey gate

rows : Map<string, Job> rows = Map.empty · admit a job verdict — row count 0 
// admit a job; the gate is one ContainsKey check
let rows, verdict = enqueue "JOB-A1" payload rows
// admit one to begin
empty queue · admit a job by id to watch the gate verdict

The whole of deduplication, at the bus, is one question: is this id already a key? A branded id is minted once, so asking it is asking "have I seen this job before" — and the answer is O(log n) in the map.

EchoMQ in F#

Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

The interactive above is not a toy version of the bus — it is the bus's admission, drawn. The echo_fs port holds each queue's rows in a Map keyed by id, and Store.enqueue checks that map before it writes. The check is the dedup:

// echo_fs/EchoMQ/Store.fs — verbatim
if st.Rows.ContainsKey id then
    st, Admission.Duplicate
else
    let row = Job.create id payload
    { st with
        Rows = st.Rows.Add(id, row)
        Pending = st.Pending.Add id },
    Admission.Enqueued

Admission is a discriminated union — Enqueued | Duplicate (echo_fs/EchoMQ/Job.fs) — so the verdict is a value the caller matches on, not a thrown error. Enqueueing the same id twice is safe: the second call returns Admission.Duplicate and the row count stays at one. Because a branded id is time-ordered and Base62 sorts as the integers do, the same dedup map keeps the pending set in mint order — dedup and ordering fall out of one structure.

The in-memory Map is the working store today. The Valkey-backed EchoMQ.Connector lands next and keeps the same admission contract: an idempotent enqueue that refuses a duplicate id.

The F# idiom

List.distinct, a Set, or a Map keyed by a key — pick by cost and by lifetime.

The bus's use

Store.enqueue is the Map case: a ContainsKey gate on a branded id makes enqueue idempotent.

Where this leads

Deduplication answers "should this job be admitted at all". The next recipe answers the question that comes after admission — whose job is served next, and how the bus keeps one busy group from draining the worker. That is priority, and the surprise is that fairness is not a sort.

↑ C4.10 · Practical recipes C4.10.2 · Priority → C4.10.3 · Windowing

References

Sources

Related in this course