haskellScott

One of the consequences of the Scott encoding is that algebraic data types are not needed; instead newtypes in combination with "forall" (parametric polymorphism) can be used to encode the case analysis of algebraic data types. This is illustrated for a Scott-encoded variation on the Contribution:haskellVariation, which involves an algebraic data type for subunits of departments (being either an employee or a department).

Illustration

Consider the straightforward algebraic data type for subunits in a company:

-- | A sub-unit is either an employee or a sub-department
data SubUnit = Employee Employee | Department Department
 deriving (Eq, Read, Show)

When using the Scott encoding, then the data type is defined as follows:

-- | A sub-unit is either an employee or a sub-department
newtype SubUnit
      = SubUnit { getSubUnit ::
          forall x. (Employee -> x)
                 -> (Department -> x)
                 -> x }

Thereby, a value of type SubUnit would essentially describe case analysis on the forms of subunits. The result type is forall-quantified, as need to perform arbitrary case analyses with arbitrary result types.

The following functions can be used instead of the constructors of an algebraic data type.

-- | Construct a subunit from an employee
employee :: Employee -> SubUnit
employee e = SubUnit (\f   -> f e)

-- | Construct a subunit from a department
department :: Department -> SubUnit
department d = SubUnit (\  f -> f d)

For instance, the cut function would need to take this form now with the only changes affected the helper function cutS which directly examines and reconstructs subunits:

-- | Cut all salaries in a company
cut :: Company -> Company
cut (n, ds) = (n, (map cutD ds))
  where
    -- Cut all salaries in a department
    cutD :: Department -> Department
    cutD (n, m, sus)
      = (n, cutE m, map cutS sus)
      where
        -- Cut the salary of an employee in half
        cutE :: Employee -> Employee
        cutE (n, a, s) = (n, a, s/2)
        -- Cut all salaries for a subunit
        cutS :: SubUnit -> SubUnit
        cutS s
          = getSubUnit s
                       (employee . cutE)
                       (department . cutD)