haskellFunctorial

Headline

Using functorial map and fold to access company data

Characteristics

Company data is quite hetereogenous. It's a container of kinds. There is a company (at the top); there is departments and employees in the tree-like structure of a company; there is also names (of employees, departments, and companies); further, there are addresses (of employess), and there are salaries of employees including managers as a special kind of employees.

We would like to access company structures in a functorial style. We have in mind the common operations Feature:Total and Feature:Cut. For these operations to fit into the functorial framework, we need to parametrize the company types appropriately in terms of salary-type positions.

Illustration

We need companies and descendants to be parametrized in salaries:

data Company s = Company Name [Department s]
...

We perform salary cut by functioral map:

cut :: Company Float -> Company Float
cut = fmap (/2) 

To this end, we assume the Company type to be parametrized in salary positions.

Likewise, we total salaries by an application of the foldr function:

total :: Company Float -> Float
total = foldr (+) 0

Here, we leverage the fact that we can access all type-parameter positions in a monoidal manner and hence essentially reduce all salaries.

Architecture

Company data model parameterized in salary position

We set up compamy data in a parameterized manner as follows:

-- The data model is parameterized in what's going to be Float-based salaries
data Company s = Company Name [Department s]
 deriving (Eq, Read, Show)
data Department s = Department Name (Manager s) [Department s] [Employee s]
 deriving (Eq, Read, Show)
data Employee s = Employee Name Address s
 deriving (Eq, Read, Show)
type Manager s = Employee s
type Name = String
type Address = String

Companies as functors over salaries

Here are the Functor instances:

instance Functor Company
  where
    fmap f (Company n ds) = Company n ds'
      where
        ds' = map (fmap f) ds

instance Functor Department
  where
    fmap f (Department n m ds es) = Department n m' ds' es'
      where
        m' = fmap f m
        ds' = map (fmap f) ds
        es' = map (fmap f) es

instance Functor Employee
  where
    fmap f (Employee n a s) = Employee n a (f s)

Companies as foldables over salaries

Here are also the Foldable instances -- we exploit the property of the Foldable type class, that the minimal definition in an instance can consist of either foldr or foldMap, as the counterpart and all other members of Foldable are universally predefined; it turns out that foldMap is straightforward to define for companies, even though one could argue that the following code isn't efficient, for example, in terms of the use of concat.

instance Foldable Company
  where
    foldMap f (Company _ ds) = ds'
      where
        ds' = mconcat (map (foldMap f) ds)

instance Foldable Department
  where
    foldMap f (Department _ m ds es) = m' `mappend` ds' `mappend` es'
      where
        m' = foldMap f m
        ds' = mconcat (map (foldMap f) ds)
        es' = mconcat (map (foldMap f) es)

instance Foldable Employee
  where
    foldMap f (Employee _ _ s) = f s

Discussion

The example demonstrates an important limitation of the functorial approach: we need to assume that a data structure can be usefully parameterized in an "element" type of a "container" type. This makes semse for actual container types such as lists or rose trees, but it is not entirely useful for more heterogeneous data structures such as companies breaking down into departments, employees, names, addresses, and salaries. In theory, we could expose "views" on copanies so that the substructure of interested is "exposed" via the type parameter, but such a conversion back and forth between custom views would be both expensive and possibly confusing.

See Contribution:haskellNonfunctorial for a more idiomatoc approach of generalizing cut to a higher-order function. Ultimately, we could leverage Theme:Haskell genericity to perform traversals on heterogeneous data structures; see, for example, Contribution:haskellSyb.