Math.MetricSpace

A MetricSpace is a set together with a notion of distance between elements. Distance is computed by a function dist which has the following four laws:

1. non-negative: forall x y. dist x y >= 0
2. identity of indiscernibles: forall x y. dist x y == 0 <=> x == y
3. symmetry: forall x y. dist x y == dist y x
4. triangle inequality: forall x y z. dist x z <= dist x y + dist y z

See the Wikipedia article on metric spaces for more details.

Documentation

>>> import qualified Data.Vector as V

newtype MetricSpace a b

Constructors

MetricSpace

Fields

dist :: a -> a -> b

Instances

Profunctor MetricSpace

SwappedMetricSpace MetricSpace

Monad (MetricSpace a)

Functor (MetricSpace a)

Applicative (MetricSpace a)

Monoid b => Monoid (MetricSpace a b)

Semigroup b => Semigroup (MetricSpace a b)

type ClosedMetricSpace a = MetricSpace a a

newtype FlippedMetricSpace b a

Constructors

FlippedMetricSpace (MetricSpace a b)

Instances

SwappedMetricSpace FlippedMetricSpace

Contravariant (FlippedMetricSpace b)

Monoid b => Divisible (FlippedMetricSpace b)

type ClosedFlippedMetricSpace a = FlippedMetricSpace a a

(<->) :: MetricSpace a b -> a -> a -> b infixl 8

_FlippedMetricSpace :: Iso (MetricSpace a b) (MetricSpace x y) (FlippedMetricSpace b a) (FlippedMetricSpace y x)

class SwappedMetricSpace m where

Minimal complete definition

Nothing

Methods

_SwappedMetricSpace :: Iso (m a b) (m x y) (m a b) (m x y)

Instances

SwappedMetricSpace FlippedMetricSpace

SwappedMetricSpace MetricSpace

levenshtein :: Integral b => MetricSpace String b

Levenshtein distance between Strings.

>>> dist levenshtein "foo" "bar"
3

>>> dist levenshtein "hi" "ha"
1

>>> dist levenshtein "ff" "ff"
0

discrete :: (Eq a, Integral b) => MetricSpace (Vector a) b

Discrete distance over n-dimensional Vectors.

>>> dist discrete (V.fromList [3,4]) (V.fromList [3,4])
0

>>> dist discrete (V.fromList [1,49]) (V.fromList [3,-94])
1

euclidean :: RealFloat a => MetricSpace (Vector a) a

Euclidean distance over n-dimensional Vectors.

>>> dist euclidean (V.fromList [3,4]) (V.fromList [3,4])
0.0

>>> dist euclidean (V.fromList [1,49]) (V.fromList [3,-94])
143.01398533010678

taxicab :: RealFloat a => MetricSpace (Vector a) a

Taxicab distance over n-dimensional Vectors.

>>> dist taxicab (V.fromList [3,4]) (V.fromList [3,4])
0.0

>>> dist taxicab (V.fromList [1,49]) (V.fromList [3,-94])
145.0