Definitions for partial algebras

[non]

Over in Spire, @denisrosset is submitting a PR to add partial algebras.

(Essentially, these operations would provide partialCombine(A, A): Option[A] instead of the more usual combine(A, A): A.)

The most natural way to do this is to make Semigroupoid[A] a parent of Semigroup[A], PartialMonoid[A] the parent of Monoid[A], and Groupoid[A] the parent of Group[A]. However, if Algebra doesn't want to add partial algebras, then obviously this would not be possible, and instead we would need to provide conversions from Group[A] => Groupoid[A] and so on.

What do you all think?

[johnynek]

I start to wonder if we need this right away. For instance, I think one goal we have is that spire and algebird ship with their types being subtypes of the appropriate algebra type. I would rather ship a version here, accomplish the above goal, and then add partial algebras.

What laws would we add? For instance is left associative always equal to right associative, or a weaker one: only if both left and right are defined are they equal. There is an interesting (to me) systems reason to want the latter, but it feels a bit unprincipled or at least I don't know much about it, so I didn't merge yet: https://github.com/twitter/algebird/pull/333

Next: where do we stop? Is there a PartialSemilattice? Partial all the things! What about using any Monad instead of just the Option Monad? So we have Semigroup[Option, T] or Semigroup[Identity, T] for the usual case? (I don't really like this option but my point is that I think we have not fully baked the partial algebras yet to include them here).

[non]

Yeah that's a totally fair point.

I think we'll want this eventually but I agree that there's a looming infinite regress. It makes me wonder about creating something like Partial[M[_], A[_]] or similar to try to handle the "general" case.

[non]

This is just to clarify my own thoughts: we probably don't want to generalize over arbitrary monads, since the implementor is going to need to be able to "wrap" a single value (ok) or return an empty value, which is a lot more specific to something like Option[_].

If anything, I would prefer to go the opposite direction and define a custom Option-like value class: it would not permit nesting but could also avoid allocations.

[denisrosset]

The Option-like value class is easy if the wrapped type is <: AnyRef, by using null as a special value; for <: Any I don't have a generic solution.

Name-based extractors can be used then without additional allocations.

Have a look at https://github.com/denisrosset/alasc/blob/6bf328962891c3733d798a9575f89ba04c50e9d9/core/src/main/scala/net.alasc/util/RefOption.scala

[denisrosset]

@johnynek :

What laws would we add? For instance is left associative always equal to right associative, or a weaker one: only if both left and right are defined are they equal.

There are two types of definitions for partial structures, the first come from category theory (and need to define source and target objects for morphism), and the second are purely algebraic. If you want an algebraic definition compatible with the categorical one, the weaker version is the one to use:

The relevant semigroupoid law can be extracted from the Groupoid page on Wikipedia (the semigroupoid page has only the category-theoretical definition):

Associativity: If a * b and b * c are defined, then (a * b) * c and a * (b * c) are defined and equal. Conversely, if either of these last two expressions is defined, then so is the other (and again they are equal).

... and it is also the version of associativity that makes sense when dealing with partial actions defined using partial algebras.

I agree that everything can be made partial. However, partial algebras describing transformations are very useful when dealing with objects of different "shapes", where the transformations need a corresponding shape to be defined -- this fits well with Scala uses in data processing.

[non]

You can actually do even better with non-boxing options. Here's some code that will box the Int into an Integer but won't allocate another object: it works with primitives and with reference types.

https://gist.github.com/non/dc01a01e3a3f830e7d4d

[denisrosset]

Great, nice usage of ==! do you plan to have Nullbox in some library in the future ?

[denisrosset]

I start to think that the right interface to put in non/algebra is a PartialFunction-like interface, with two methods:

• isOpDefined(x: A, y: A): Boolean and
• op(x: A, y: A): A which is defined only when isOpDefined(x, y) is true.

This leaves other libraries the option of defining a partialOp with a specific encoding (Option, Nullbox ?) internally.

[denisrosset]

I think that issue can be closed. Partial algebras encourage partial functions; we merged them into Spire, but I'm leaning towards splitting them in a separate library.