Susan Potter

No subtyping in PureScript

Fri September 9, 2020

DRAFT

This is an excerpt from a code review that I sanitized for public consumption. Changes include modifying code examples to not refer to internal types or domains:


PureScript (like Haskell) has zero notion of subtyping. Subtyping is often paired with inheritance in OO languages to derive moderate amounts of reuse from class-based hierarchies. Today, the OO community appears to prefer OO "composition" over inheritance (https://en.wikipedia.org/wiki/Composition_over_inheritance).

Typically OO composition yields simpler and more practical solutions to problems beyond the toy examples found in OO textbooks back in the day. Interestingly, Alan Kay disputes that OO is about inheritance (it's about "message passing" to him).

So, since we don't have subtyping, you might be wondering what the data constructors in an algebraic data type's definition are about?

These are not subtypes. It does not inherit any behavior, a data constructor is just one valid way of constructing values for its type.

Consider:

data Shape
  = Square { length :: Number }
  | Rectangle { width :: Number, height :: Number }
  | Circle { radius :: Number }

In the above data definition we have defined a type named Shape. It has three data constructors (Square, Rectangle, and Circle). These are functions that have a capitalized first character for the name. If you look at their types you will see they are basically just functions with names that look a different than usual:

>>> :t Square
Square :: Number -> Shape

>>> :t Rectangle
Rectangle :: Number -> Number -> Shape

>>> :t Circle
Circle :: Number -> Shape

At the type-level it doesn't have subtypes of Square, Rectangle, or Circle. They are just data constructors which are simply functions with beginning with a capital letter. They define a way to construct valid values of the type Shape. That's it.

Now, back to the original crux of your question: how would we be able to share structural definitions across types?


Ok, next installment. How can we share the structure of a type definition?

In OO languages we would use subtyping to get interface compatibility. The reason this felt so necessary in OO is that this paradigm couples data definition and object behavior together fairly tightly (you put methods in your class definition which contains your data structure and exposes getters/setters/modifiers as well as side-effecting behavior).

In functional programming (FP) we define the data definition and then functions that consume or produce this data more independently although they can both be packaged together in the same module for coherence when that is useful (for data hiding/encapsulation, etc.).

So what we want in FP isn't subtyping but rather the ability to share the structure of a data definition across type definitions.

Let's introduce the following data types and functions:

data Employee
  = MkEmployee { firstName :: String, lastName :: String, title :: String, address :: Address }

data Customer
  = BusinessEntity { legalName :: String, address :: Address, contacts :: Array Contact }
  | Individual { firstName :: String, lastName :: String, address :: Address }

data Contact
  = MkContact { firstName :: String, lastName :: String, title: String, address :: Address }

data Address
  = MkAddress { streetAddress1 :: String, streetAddress2 :: String, city :: String, state :: String, zipcode :: String }

data Suffix = Jr | Sr
data Prefix = Dr | Professor

addSuffix :: Suffix -> Employee -> Employee
addSuffix Jr emp = emp { lastName = emp.lastName <> ", Jr." }
addSuffix Sr emp = emp { lastName = emp.lastName <> ", Sr." }

addPrefix :: Prefix -> Employee -> Employee
addPrefix Dr emp = emp { firstName = "Dr. " <> emp.firstName }
addPrefix Professor emp = emp { firstName = "Prof. " <> emp.firstName }

-- Exercise for the reader! :)
addSuffix :: Suffix -> Contact -> Contact
addPrefix :: Prefix -> Contact -> Contact

Ok, so the issue here is that we might want to support addSuffix and addPrefix for all data type definitions that have a lastName :: String and firstName :: String fields respectively, but being different types we end up defining two variants even though essentially they are the same.

We can solve this in multiple ways in PureScript. We could define an "interface" via a typeclass and instances for each data type, but then we have duplication of the implementations for these "methods". Another type facility we have is structural typing which has two variations: polymorphic row types and polymorphic variants.

What we would want is the first variation, row polymorphism, for this case:

addPrefix' :: Prefix -> { firstName :: String } -> { firstName :: String }
addPrefix' Dr prefixable = prefixable { firstName = "Dr. " <> prefixable.firstName }
addPrefix' Professor prefixable = prefixable { firstName = "Prof. " <> prefixable.firstName }