Create a new version for a space efficient monoid

eborden commented 7 years ago

The list based monoid representation is not space efficient. This implementation also leads towards a number of confusing and highly opinionated instances. This new implementation is space efficient, ideal for on-line algorithms and does not include possibly confusing/problematic instances.

This addresses feedback in https://github.com/hanshoglund/average/issues/3

This may seem like an aggressive PR. I recognize that. However I believe this package name is too high value for it to be populated by an inefficient implementation.

eborden commented 7 years ago

Hmmm, I'm trying to remember what case I found incomprehensible with pure = Average 1, but it seems to be good.

eborden commented 7 years ago

Right, now I found where Num becomes incoherent. Check the results for + and * laws:

  laws for: Num
    addition
      associativity
      commutative
      left identity FAILED [1]
      right identity FAILED [2]
    multiplication
      associativity
      commutative
      left identity FAILED [3]
      right identity FAILED [4]

eborden commented 7 years ago

Applicative is also in a terrible state with the current instance:

  laws for: applicative
    identity FAILED [1]
    composition FAILED [2]
    homomorphism FAILED [3]
    interchange
    functor FAILED [4]

eborden commented 7 years ago

Also to be clear the 0.6 version of this library is also violating laws:

Average
  laws for: monoid
    left  identity
    right identity
    associativity
  laws for: functor
    identity
    compose
  laws for: applicative
    identity
    composition
    homomorphism
    interchange
    functor
  laws for: Num
    addition
      associativity
      commutative FAILED [1]
      left identity
      right identity
    multiplication
      associativity
      commutative FAILED [2]
      left identity
      right identity
  laws for: vector space
    associativity
    commutative FAILED [3]
    left identity
    right identity
    closure
      distributive: c u v
      distributive: c d v FAILED [4]
      associativity
      unitary

eborden commented 7 years ago

Current test results:

Average
  laws for: monoid
    left  identity
    right identity
    associativity
  laws for: functor
    identity
    compose
  laws for: additive group
    associativity
    commutative
    left identity
    right identity

Finished in 0.0061 seconds
9 examples, 0 failures

eborden commented 7 years ago

Note there may be some desire here to preserve pure through Pointed, but I'd urge against that and point to this: https://wiki.haskell.org/Why_not_Pointed%3F

hanshoglund commented 7 years ago

Thanks for the detailed PR and for pointing out the lawbreaking instances.

I like this a lot and would be happy to merge except that it breaks my original use-case for the library: namely to have a drop-in replacement for Sum and Product supporting Eq, Ord and Fractional.

I agree that the list version should be dropped but would like to have a replacement for for the original use-case under a different module space (and documentation of the tradeoffs). I'm pretty sure that the commutative/distributive laws could be fixed by using a free group instead of a list, will give that a go tomorrow.

leftaroundabout commented 7 years ago

@eborden You've now basically reduced everything to monoid. (Your AdditiveGroup instance is just a synonym for the Monoid one.)

That makes perhaps sense if Monoid and Functor is all we can fulfill the laws for, however in that case I would question the sensibility of pretending there's any more structure. Why would we need AdditiveGroup if it's just a synonym for Monoid, together with fmap?

For that matter, does the Functor instance really make sense? As I see it, Average values should always describe the (...duh) average, and any weights or lists are merely an implementation detail. Thus, I'd think fmap should basically operate on the values in the order of magnitude. The old list implementation did offer that behaviour.

With this new approach however, fmap operates usually on a highly magnified value, basically on avg * weight. That means that mapping a nonlinear operation will give crazy results.

I personally think that we should either

Remove anything that might cause surprise, keep only the Monoid instance.
Find an implementation for which the other instances actually behave sensibly. One possibility would be to compute the average before any Functor or VectorSpace operation; the problem, as I said, is that this doesn't allow full parametricity. But perhaps MonoFunctor is a better fitting abstraction here anyway:
```
type instance Element (Average a) = a
instance Fractional a => MonoFunctor (Average a) where
  omap f (Average w x) = Average w $ w' * f (x / w')
   where w' = fromIntegral w
```
Another option would be to just store the averages right away. That would allow keeping the derived Functor instance, but it would require changing the monoid instance:
```
instance Fractional a => Monoid (Average a) where
  mempty = Average 0 0
  Average w x <> Average ψ ξ = Average wψ $ (fromIntegral w * x + fromIntegral ψ * η)
                                                  / fromIntegral wψ
     where wψ = w + ψ
```

leftaroundabout commented 7 years ago

In fact, I've discovered another law violation:

Average 1 1 ^+^ negateV (Average 1 1) ≡ Average 1 0
       ≠ zeroV ≡ Average 0 0

...unless you treat the weights as an implementation detail, but you can't, because Average 1 0 is observably different from mempty via

getAverage (Average 1 0 <> Average 1 1) ≡ 1/2
     ≠ 1 ≡ getAverage (Average 1 1)

leftaroundabout commented 7 years ago

Exploring the second approach in https://github.com/leftaroundabout/average/tree/refactor/weight-and-average

eborden commented 7 years ago

Yes, the additive group does not seem to make sense since we can't reliably provide a negateV instance that doesn't explode. However I feel the Functor instance is still useful. It allows you to lift operations into the Average. fmap (* 3) $ Average 2 6 == Average 2 18.

Curious to see where your exploration leads.

leftaroundabout commented 7 years ago

@eborden sure the functor instance is useful, but when storing a running sum it only works with linear functions (like negate or (^*3). Thus that should really be

instance CCat.Functor (-+>) (-+>) Average

with the generalised Functor class in the (-+>) category.

But I don't think it's feasible for this package to depend on linearmap-category...

leftaroundabout commented 7 years ago

@eborden I made a new PR #5 out of these thoughts. All of your original tests for Monoid, Num etc. succeed, however I think these were actually not strong enough: they permit different weights, but different weights can lead to different behaviour as in that negation-cancellation example.

Even when checking weights, only the distributive law fails.

All the numerical / vector laws are fulfilled when merely working with “pure values”, but they now generalise quite naturally to impure values as well.

hanshoglund / average

Create a new version for a space efficient monoid #4