Design and Analysis of Algorithms

584 Design and Analysis of Algorithms

4. map equality: Two maps, f and g, are equal if and only if they have the same domain and their application

on every domain element is identical. This can be expressed formally as:

f = g ⇔

dom f = dom g ∧ ∀ x ∈ dom g · f (x) = g(x)

Given these operations, the characteristic of any map f can be summed up by the logic condition:

∀ a, b ∈ dom f · a = b ⇒ f (a) = f (b)

There are more operations associated with the map type, notably map comprehension which is similar

in operation to the set comprehension technique.

20.4.3 A Small Example

This example shows the standard mergesort algorithm, well known from ...