Approximately equal

[Chris Marshall]

For a type A which is a Semigroup with an Order, it's possible to define a function "approximately equal" as follows:

  scala> implicit class X[A: scalaz.Order: Semigroup](self: A) {

     |   def =~=(that: A)(implicit ε: A) = {

     |     val cf = Order[A].order(self, that)

     |     if (cf == Ordering.EQ) true

     |     else if (cf == Ordering.LT) (self |+| ε) >= that

     |     else (that |+| ε) >= self

     |   }

     | }

  defined class X

The use of this is something like:

  scala> implicit val epsilon = 0.1 

  epsilon: Double = 0.1

  scala> 1D =~= 2D

  res0: Boolean = false

  scala> 1D =~= 1.01D

  res1: Boolean = true

  scala> 1.01D =~= 1D

  res3: Boolean = true

If I were to add this as a PR, where would I put it? On OrderOps? Is there some reason this is a bad idea?

Why is this useful? When doing floating point math with e.g. trading quantities, I may want to check that a book is flat at the end of the day. However, the residual dollar value present in the book might be a very small number like 1E-7. Obviously I could do something like:

  assert(book.positions filterNot (_.dollarValue.abs <= 0.001) isEmpty)

But I prefer 

  implicit val ε = 0.001 

  assert(book.positions forall (_.dollarValue =~= 0D)

As I believe it's more expressive

Chris

[Stefan Hoeck]

+1

Seems to be very useful.

[Paul Chiusano]

I really don't like taking a 'naked' implicit A there, with no meaning attached, but I also don't like having a lawless trait Epsilon[E] { def epsilon: E }. The epsilon is with respect to some operation and ordering, so if we want to add this, it seems like it belongs somewhere in a more complete numerical tower than exists right now. 

So IMO, I don't think this belongs in Scalaz yet. 

Paul

--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scalaz+un...@googlegroups.com.
To post to this group, send email to sca...@googlegroups.com.
Visit this group at http://groups.google.com/group/scalaz?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Tom Switzer]

Chris,

I made a PR to Spire based on your new operator, but using metric spaces: https://github.com/non/spire/pull/97

Your use case would look something like this:

    implicit val ε = MetricSpace.Epsilon[Double, Double](0.001)

    assert(book.positions forall (_.dollarValue =~= 0D)

We can also approximately compare anything in a metric space now:

    implicit val ε = MetricSpace.Epsilon[String, Int](1)

    assert("Thomas" =~= "thomas")

I'm not entirely happy with how the epsilon is defined. Preferably, I'd use a dependent type, but the problem is that a lot of MetricSpace instances are recreated with each use (eg. anything that can be embedded in the reals, like Double).

The current Epsilon is tied to both the metric space and the "real" number distances are measured in, which makes it a bit more precise, but seems hacky to me.

Any ideas?

Cheers,

Tom

On Fri, May 17, 2013 at 1:46 PM, Tom Switzer <thomas....@gmail.com> wrote:

So, this seems like it may be a useful operator in Spire. However, I feel that using a Semigroup generalizes in one direction, but takes away in another. Namely, it means your notion of "closeness" has to exist within the same type as your semigroup. Think of points in euclidean space for instance; the intuitive notion of whether x =~= y is tied to their euclidean distance, not point addition.

I quickly whipped up something, based on your work above, but generalized to metric spaces:

https://gist.github.com/tixxit/5601424

This would work as expected for types like Int, Double, BigDecimal, etc. but it'd also let us approximately compare vectors, strings (using edit distance), etc.

What do you think?

This would be for inclusion in Spire.

--

[etorreborre]

Is it possible to create a "range calculus" where each value encapsulates the admissible range?

So instead of writing:

dollarValue =~= 0D

"Thomas"   =~= "thomas"

You would write (nice syntax TBD)

range(dollarValue, 0.001) =~= range(0D, 0.001)

range("Thomas", MetricSpace.Epsilon[String, Int](1)) =~= range("thomas", MetricSpace.Epsilon[String, Int](1))

This would also let you do comparisons on things having different "epsilons".

E.

[Tom Switzer]

I like this idea -- think about =~= as seeing if 2 balls intersect. I think Erik would like this too, since it means =~= generalizes sanely to Spire's Interval (and Scala's Range, etc). It is also nice to get rid of the implicit epsilon. For metric spaces, the range function could always take a double too, so range("thomas", 1) =~= range("Thomas", 1) would work just fine.

[Tom Switzer]

So, Erik, what I'm thinking is that with your ApproxEq then, we basically have a Neighbourhood[V, A](v: V, r: A)(implicit ms: MetricSpace[V,A]) that can be constructed from the range function (or what-have-you). We then have an ApproxEq instance for any Neighbourhood[V, A].

[Chris Marshall]

I like this approach (metric spaces are the appropriate construct to use here, of course) but am not sure about why all the type parameters are needed. I'm not familiar with Spire, I'm afraid, but presumably a MetricSpace[A] is just defined as follows:

  trait MetricSpace[A] {

    def distance(a1: A)((a2: A): Double

  }

Together with the laws:

  forall X, distance(X)(X) == 0

  forall X, Y, distance(X)(Y) == diance(Y)(X)

  forall X, Y, Z, distance(X)(Y) + distance(Y)(Z) <= distance(X)(Z)

We can then define =~= (which is now a measure of "closeness", rather than equality, so I'd drop the operator implying approximate equality)

  trait Epsilon

  def epsilon(d: Double): Double @@ Epsilon = d.asInstanceOf[Double @@ Epsilon]

  implicit class MetricSpacePoint[A: MetricSpace](a: A) { def isCloseTo(y: A)(implicit val eps: Double @@ Epsilon) = MetricSpace[A].distance(a)(y).abs <= eps.abs } }

  

So that:

  implicit val e = epsilon(0.001)

  1 isCloseTo 1.1

I suppose you might want to tag the epsilon by your space (so that an epsilon intended for Euclidean space couldn't be mistaken for one in hyperbolic space). Perhaps you might use dependent types for this? That is:

  trait MetricSpace[A] {

    type Distance <: Double

    def distance(a1: A)((a2: A): Distance

  }

And:

  implicit class MetricSpacePoint[A](a: A)(implicit M: : MetricSpace[A]) { 

    def isCloseTo(y: A)(implicit val eps: M.Distance) = M.distance(a)(y).abs <= eps.abs } 

  }

(That's probably not correct - I'm no replacement for Miles)

Chris

(This doesn't work in scalaz, where their definition of a metric space has an integral distance). 

[Lars Hupel]

> (This doesn't work in scalaz, where their definition of a metric space has
> an integral distance).

Note that, if you'd like to use `MetricSpace`, it is going to go away in
scalaz (it'll already be deprecated in 7.0.1 and is scheduled for
removal in 7.2). The (few) instances we had and the laws are already
included in spire.

[Chris Marshall]

I can't get the dependently-typed example working without losing the "implicit"-ness of the metric Space. Here's some code, though:

scala> trait MetricSpace[A] { type Distance <: Double; def distance(a: A, b: A): Distance }

defined trait MetricSpace

scala> implicit val RealLine = new MetricSpace[Double] {

     | type Distance = Double

     | def distance(a: Double, b: Double) = (a - b).abs

     | }

RealLine: MetricSpace[Double]{type Distance = Double} = $anon$1@a9486f71

scala> implicit val eps: RealLine.Distance = 0.011

eps: RealLine.Distance = 0.011

Then, the messy bit

scala> implicit class MetricSpacePoint[A](a: A) {

     | class OnThe(val b: A) { def onThe(M: MetricSpace[A])(implicit eps: M.Distance) = M.distance(a, b) <= eps }

     | def isCloseTo(b: A) = new OnThe(b)

     | }

defined class MetricSpacePoint

So that I can do:

scala> 1D isCloseTo 1.01D onThe RealLine

res8: Boolean = true

I think that normal tagged types are preferable for the epsilon, as per my previous email

Chris

[Tom Switzer]

Hi Chris,

From a Spire perspective, 2 parameter types is ideal:

  1) it meshes well with our vector space type classes (eg. NormedVectorSpace[V, A] extends MetricSpace[V, A]),

  2) abstract types are not @specialized-able and we want to be able to avoid boxing where possible, and

  3) Spire is aimed at generic numerics, so tying ourselves down to Double would not be ideal.

For 3), for instance, the metric space of Rational should not map to a Double, you lose precision!

For metric spaces, we tie the scalar type down an `IsReal`, which is how we witness that a type is embeddable in the reals. It has nice methods like a _.toDouble approximation if you need it :)

What do you think of Eric's proposal?

Thanks,

Tom