Design pattern for subclass-like structure

Question

My goal is to represent a set of types with a similar behaviour in a elegant and performant manner. To achieve this, I have created a solution that utilises a single type, followed by a set of functions that perform pattern matching.

My first question is: is there a way how to represent the same ideas using a single type-class and instead of having a constructor per each variation to have a type that implements said type-class?

Which of the two approaches below is: - a better recognised design pattern in Haskell? - more memory efficient? - more performant? - more elegant and why? - easier to use for consumers of the code?

Approach 1: Single type and pattern matching

Suppose there is a following structure:

data Aggregate a
  = Average    <some necessary state keeping>
  | Variance   <some necessary state keeping>
  | Quantile a <some necessary state keeping>

It's constructors are not public as that would expose the internal state keeping. Instead, a set of constructor functions exist:

newAverage :: Floating a
  => Aggregate a
newAverage = Average ...

newVariance :: Floating a
  => Aggregate a
newVariance = Variance ...

newQuantile :: Floating a
  => a                     -- ! important, a parameter to the function
  -> Aggregate a
newQuantile p = Quantile p ...

Once the object is created, we can perform two functions: put values into it, and once we are satisfied, we can get the current value:

get :: Floating a
  => Aggregate a
  -> Maybe a
get (Average <state>) = getAverage <state>
get (Variance <state>) = getVariance <state>
get (Quantile _ <state>) = getQuantile <state>

put :: Floating a
  => a
  -> Aggregate a
  -> Aggregate a
put newVal (Average <state>) = putAverage newVal <state>
put newVal (Variance <state>) = putVariance newVal <state>
put newVal (Quantile p <state>) = putQuantile newVal p <state>

Approach 2: Type-classes and instances

class Aggregate a where
  new :: a
  get :: Floating f => a f -> Maybe f
  put :: Floating f => 

data Average a = Average Word64 a
data Variance a ...

instance Aggregate Average where

instance Aggregate Variance where

instance Aggregate Quantile where

The obvious problem here is the fact that new is not parametric and thus Quantile can't be initialised with the p parameter. Adding a parameter to new is possible, but it would result in all other non-parametric constructors to ignore the value, which is not a good design.

Answer 1

You are missing the "codata" encoding, which sounds like it might be the best fit for your problem.

data Aggregate a = Aggregate 
    { get :: Maybe a
    , put :: a -> Aggregate a
    }

-- Use the closure to keep track of local state.
newAverage :: (Floating a) => Aggregate a
newAverage = Aggregate { get = Nothing, put = go 0 0 }
    where
    go n total x = Aggregate { get = Just ((total + x) / (n+1))
                             , put = go (n+1) (total+x)
                             }

-- Parameters are not a problem.
newQuantile :: (Floating a) => a -> Aggregate a
newQuantile p = Aggregate { get = ... ; put = \x -> ... }

...

For some reason this approach always slips under the radar of people with OO backgrounds, which is strange because it is a pretty close match to that paradigm.

Answer 2

There is a third approach for defining “aggregators” that neither requires an inextensible sum type nor multiple datatypes + a typeclass.

Approach 3: Single-constructor datatype that puts state behind an existential

Consider this type:

{-# LANGUAGE ExistentialQuantification #-}
data Fold a b = forall x. Fold (x -> a -> x) x (x -> b)

It represents an aggregator that ingests values of type a and eventually "returns" a value of type b while carrying an internal state x.

The constructor has type (x -> a -> x) -> x -> (x -> b) -> Fold a b. It takes a step function, an initial state and a final "summary" function. Notice that the state is decoupled from the return value b. They can be the same, but it's not required.

Also, the state is existentially quantified. We know the type of the state when we create a Fold, and we can work with it when we pattern-match on the Fold—in order to feed it data through the step function—but it's not reflected in the Fold's type. We can put Fold values with different inner states in the same container without problems, as long as they ingest and return the same types.

This pattern is sometimes called a “beautiful fold”. There is a library called foldl that is based on it, and provides may premade folds and utility functions.

The Fold type in foldl has many useful instances. In particular, the Applicative instance lets us create composite folds that still traverse the input data a single time, instead of requiring multiple passes.

Answer 3

It's hard to give a general recommendation. I tend to prefer approach 1. Note that you could use

data Aggregate a
  = Average    AverageState
  | Variance   VarianceState
  | Quantile a QuantileState

and export every constructor above, keeping only the ...State types private to the module.

This might be feasible in some contexts, but not in others, so it has to be evaluated on a case by case basis.

About approach 2, this could be more convenient if you have many constructors / types around. To fix the new problem, one could use type families (or fundeps) as in

class Floating f => Aggregate a f where
  type AggregateNew a f
  new :: AggregateNew a f -> a f
  get :: a f -> Maybe f
  put :: ...

instance Floating f => Aggregate Average f where
  type AggregateNew (Average a) f = ()
  new () = ...

instance Floating f => Aggregate Quantile f where
  type AggregateNew (Quantile a) f = a
  new x = ...

The naming above is horrible, but I used it to make the point. new takes an argument of type AggregateNew k f which can be () if new needs no information, or some more informative type when it is needed, like a for creating a Quantile.