Re: Splitting Numeric to separate Sum from Product

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 09/12/2011 09:43 PM, Ben Hutchison wrote:
> On Fri, Sep 9, 2011 at 11:53 AM, Tom Switzer wrote:
>> Perhaps a trade-off could be to create a few new traits. Something more
>> like,
>> trait Monoid[A] {
>> def zero: A
>> def add(x: A, y: A): A
>> }
>>
>> trait Ring[A] extends Monoid[A] {
>> def one: A
>> def sub(x: A, y: A): A
>> def mul(x: A, y: A): A
>> }
>> trait Numeric[A] extends Ring[A] {
>> def div(x: A, y: A): A
>> }
>
> A beautiful and liberating aspect of switching from an OO- centric to
> a Typeclass- centric "default worldview" is that you no longer need to
> inherit from something to be that something. You don't need to inherit
> from Number to be a number, and you dont need to inherit from Monoid
> to be a monoid. Sum and Product are monoids, and they don't need the
> consent of the core library:
>
> implicit def sum2Monoid[A](sum: Sum[A]) = new Monoid[A] {
> def zero = sum.zero
> }
>
> Another limitation of inheritance is that it's essentially a global
> declaration. The trait hierarchy sketched above states that Numeric is
> always interpreted as a Monoid via addition/zero. But
> multiplication/one is an equally valid way to interpret Numeric as a
> Monoid. And to represent that via inheritance requires that Numeric
> inherits from Monoid twice simultaneously with differing
> implementations: a contortion not even Scala will allow!
>
> -Ben
>
>>
>> On Thu, Sep 8, 2011 at 8:30 PM, Ben Hutchison wrote:
>>>
>>> On Fri, Sep 9, 2011 at 1:26 AM, Tom Switzer
>>> wrote:
>>>> Numeric (and Fractional and Integral) is simple enough
>>>> to be understandable by most people (vs. monoids, rings, fields, etc),
>>>> while
>>>> still providing a good amount of flexibility.
>>>
>>> Actually, the problem is precisely that Numeric is not simple enough.
>>> I don't think its about adding "algebraic structure" or "monoids" into
>>> the library. Rather, simply splitting the methods already there into
>>> smaller, more focused units. I suspect that it can be done while
>>> maintaining backwards compatibility.
>>>
>>> Numeric defines Addition and Multiplication in one interface. Thats
>>> unnecessary coupling: considering TraversableOnce.{sum, product}
>>> (presently the main application/motivation of Numeric in the library),
>>> sum requires you to pass a definition of multiplication, even though
>>> it never uses it. Similarly, product requires Addition even though
>>> it's never used.
>>>
>>>
>>> chances are you are going to want
>>>> to do a lot more with your vectors than just sum them. You'd probably
>>>> want
>>>> an entire library dedicated to dealing with them.
>>>
>>> Indeed. Anyone can create such a library if they wish, using their
>>> preferred design. But how and where will it integrate with the
>>> standard library? The touchpoints may likely include sum and product,
>>> and it makes sense for the standard lib to require the minimal
>>> required interface from the provider of Numeric-like operations.
>>>
>>>> Moreover, matrices and vectors have the problem that their dimension is
>>>> an
>>>> integral part of what operations are defined. So even defining something
>>>> as
>>>> simple as Vector addition requires runtime checks with a Numeric-like
>>>> Monoid
>>>> trait. Since scala's Numeric instances seem to be wholly against runtime
>>>> exceptions (eg. implicitly[Fractional[Double]].div(1, 0) gives infinity,
>>>> rather than an exception), I'm not sure if Vectors would mix well.
>>>
>>> A counter example, from Stanford PPL's Delite project, which
>>> currently has several EPFL Scala team members working on/around it. It
>>> would seem that they see value in numeric operations over Vectors &
>>> Matrices:
>>>
>>>
>>> https://github.com/stanford-ppl/Delite/blob/develop/dsls/optiml/src/ppl/...
>>>
>>
>> I didn't mean to imply that you shouldn't able to do arithmetic over vectors
>> or matrices (it obviously makes sense), but more that I wasn't entirely sure
>> if there was a reason why Numeric seems to eschew runtime exceptions.
>>
>>>
>>> -Ben
>>>
>>> PS Delite's Arith numeric typeclass also demonstrates the diversity
>>> around how to handle the division operator, having chosen a different
>>> approach to the standard library.
>>
>> Yep. I prefer Numeric's approach, but clearly several opinions in the
>> conversation take "Arith"'s side.

trait Semigroup[A] {
def op(a1: A, a2: A): A
}

trait Monoid[A] extends Semigroup[A] {
def zero: A
}

You've no idea how much trouble it can cause if you don't split this
out. I am overwhelmed by the monstrosity of explaining why at this
moment, so please trust me for now, don't make this mistake! I can say
for now that Edward Kmett rewrote an enormous chunk of the type-class
hierarchy
and supporting libraries based on semigroups that are not monoids,
because of *just how useful this is*.

Much of Scalaz also emphasises this.

Re: Splitting Numeric to separate Sum from Product

On Mon, Sep 12, 2011 at 5:46 AM, Tony Morris <tonymorris [at] gmail [dot] com> wrote:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
trait Semigroup[A] {
def op(a1: A, a2: A): A
}

trait Monoid[A] extends Semigroup[A] {
def zero: A
}

You've no idea how much trouble it can cause if you don't split this
out. I am overwhelmed by the monstrosity of explaining why at this
moment, so please trust me for now, don't make this mistake! I can say
for now that Edward Kmett rewrote an enormous chunk of the type-class
hierarchy
and supporting libraries based on semigroups that are not monoids,
because of *just how useful this is*.

Much of Scalaz also emphasises this.

- --
Tony Morris
http://tmorris.net/

I'll go one further: please go as far as semigroup and monoid actions:
trait SAct[A, B] {   def append(a: A, b: B): A}
trait MAct[A, B] extends SAct[A, B] with Zero[A]
Then semigroups and monoids become specializations of these traits.
Kris

Re: Splitting Numeric to separate Sum from Product

On Mon, Sep 12, 2011 at 7:46 AM, Tony Morris <tonymorris [at] gmail [dot] com> wrote:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 09/12/2011 09:43 PM, Ben Hutchison wrote:
> On Fri, Sep 9, 2011 at 11:53 AM, Tom Switzer <thomas [dot] switzer [at] gmail [dot] com> wrote:
>> Perhaps a trade-off could be to create a few new traits. Something more
>> like,
>> trait Monoid[A] {
>>   def zero: A
>>   def add(x: A, y: A): A
>> }
>>
>> trait Ring[A] extends Monoid[A] {
>>   def one: A
>>   def sub(x: A, y: A): A
>>   def mul(x: A, y: A): A
>> }
>> trait Numeric[A] extends Ring[A] {
>>   def div(x: A, y: A): A
>> }

trait Semigroup[A] {
def op(a1: A, a2: A): A
}

trait Monoid[A] extends Semigroup[A] {
def zero: A
}

You've no idea how much trouble it can cause if you don't split this
out. I am overwhelmed by the monstrosity of explaining why at this
moment, so please trust me for now, don't make this mistake! I can say
for now that Edward Kmett rewrote an enormous chunk of the type-class
hierarchy
and supporting libraries based on semigroups that are not monoids,
because of *just how useful this is*.

Much of Scalaz also emphasises this.

- --
Tony Morris
http://tmorris.net/

+1 for splitting out Semigroup from Monoid.

Even if you actually could define a zero, you don't necessarily want to have to bother.  For example, if you're merging duplicate customer records, you probably don't want to have to worry about the hypothetical "zero customer" that can be merged with any other customer without causing any changes.  (Or maybe you do.  But it might be unpleasant to be _forced_ to.)

Or think about trees; if you have a join(x,y), which creates a tree
+
/ \
x   y
what could your "zero tree" possibly be (without special-casing something like flattening on null)?

--Rex