Skip to content

Instantly share code, notes, and snippets.

@reinh
Last active January 4, 2016 07:18
Show Gist options
  • Save reinh/8587382 to your computer and use it in GitHub Desktop.
Save reinh/8587382 to your computer and use it in GitHub Desktop.
Average Semigroup
=================
> {-# LANGUAGE GeneralizedNewtypeDeriving #-}
>
> module Average where
>
> import Data.Semigroup
> import Data.Ratio (Ratio, (%))
A [semigroup](http://en.wikipedia.org/wiki/Semigroup) is an algebraic structure consisting of a set together with an associative binary operation. In Haskell, that would be:
> class Semigroup a where
> (<>) :: a -> a -> a
The associativity property means that this identity must hold:
(a <> b) <> c = a <> (b <> c)
In other words, it doesn't matter how you parenthesize or group the operations.
Some examples of common semigroups include:
* The sum semigroup, of numbers with addition.
* The product semigroup, of numbers with multiplication.
* The list semigroup, of lists with concatenation.
* The cartesian product semigroup, of tuples of semigroups with pairwise combination.
In other words, if S and T are semigroups then (S,T) is a semigroup where elements are combined pairwise: (S <> S', T <> T').
An Average semigroup can be viewed as a product semigroup of two Sum semigroups: the current total and the current count.
We'll provide our own field accessor so we can retrieve the average conveniently as the ratio of total to count.
> newtype Average = Average (Sum Int, Sum Int)
> deriving (Semigroup, Eq, Ord)
>
> getAverage :: Average -> Ratio Int
> getAverage (Average (Sum n, Sum c)) = n % c
>
> instance Show Average where
> show n = "Average {getAverage = " ++ show (getAverage n) ++ "}"
Since we aren't embedding the count at the type level we have to provide our own data constructor:
> avg :: Int -> Average
> avg n = Average (Sum n, Sum 1)
Example:
--------
>>> sconcat . fmap (\n -> (Min n, Max n, avg n) $ fromList [1,2,3,1,2,3]
==> (Min {getMin = 1},Max {getMax = 3},Average {_getAverage = 2 % 1})
The lambda `\n -> (Min n, Max n, avg n)` can also be written in an applicative form as `(,,) <$> Min <*> Max <*> avg)`.
The applicative for function arrows can be handy for other sorts of constructors as well:
> data Stats = Stats
> { _min :: Min Int
> , _max :: Max Int
> , _avg :: Average
> }
>
> --- note that the product type Stats forms a cartesian product semigroup.
> instance Semigroup Stats where
> (Stats x y z) <> (Stats x' y' z') = Stats (x<>x') (y<>y') (z<>z')
>
> instance Show Stats where
> show (Stats min' max' avg') =
> "Stats min: " ++ show (getMin min') ++
> " max: " ++ show (getMax max') ++
> " avg: " ++ show (getAverage avg')
>>> sconcat . fmap (Stats <$> Min <*> Max <*> avg) $ fromList [1,2,3,1,2,3]
==> Stats min: 1 max: 3 avg: 2 % 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment