Last active
January 4, 2016 07:18
-
-
Save reinh/8587382 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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