Layered data types

Identity: Layered
Category: Data MultiModule
Classifiers: data abstraction
Internal cross references:
External cross references:

Language: This has been described in terms of Haskell, but will apply to any language with abstract data types.

Description: Commonality in a data type is factored out by the introduction of a separate type which explicitly represents the different variants within the original type.

data Expr = Lit Float |             
            Add Expr Expr |              
            Mul Expr Expr |
            Sub Expr Expr           

eval (Lit r) = r                    

eval (Add e1 e2)                    
  = eval e1 + eval e2               
eval (Mul e1 e2)                    
  = eval e1 * eval e2              
eval (Sub e1 e2)                    
  = eval e1 - eval e2                         

data Expr  = Lit Float |
             Bin BinOp Expr Expr

data BinOp = Add | Mul | Sub

eval (Lit r) = r

eval (Binop op e1 e2)
  = evalOp op (eval e1) (eval e2)

evalOp Add = (+)
evalOp Mul = (*)
evalOp Sub = (-)

General comment:

It is possible to see this refactoring first being used left to right, to allow the addition of constructors in a localised way, and then from right to left, to permit the introduction of binary functions over the data type.

Note that the application of the refactoring in either direction requires the underlying data type to be modified, and so all clients of the type, and indeed all constructors of values of the type, need to be modified.

Left to right comment:

The code on the LHS repeats the functionality of "apply the appropriate binary operator to the evaluated arguments' for the three different kinds of expression.

This commonaility is reflected in the RHS code, once the differences are factored out in the interpretation of the new data type, BinOp.

Right to left comment:

The RHS complicates the definition by introducing the layer of binary operators. It also forces all BinOps to be evaluated in the same pattern.

Left to right conditions:

The functions over the data type must exhibit a degree of common behaviour.

Right to left conditions:

There is no restriction on the right to left transition, which can be seen as the unfolding of the partical application of the Bin constructor to the BinOp type.