Adding a little something

In a previous blog, I introduced the simple addition function as a means of talking about pure functions and functional programming. The add function was defined in the functional programming language Haskell and the dynamic programming languages Python and Ruby.

In Python (and Ruby), we observed that the pure addition function we defined could add not only numbers, but strings as well:

# add.py
def add(x, y):
    return x + y
-----------------
>>> from add import add
>>> add(3, 4)   
7
>>> add("I'm a ", "String!")
"I'm a String!"
>>> add([1, 2], [3, 4, 5])
[1, 2, 3, 4, 5]

In fact, as the example above illustrates, the Python (and Ruby) functions will work for anything that implements the "addition" function (in this case, specifically the "+") including, as shown, Python lists ([3, 4, 5] is appended to [1, 2] using the "add" function or "+" method of Python lists).

As promised, in this installment, we'll look at what it takes to write the same type of polymorphic add function in Haskell.

For this post, I'm only going to write Python and Haskell. Ruby enthusiasts can play along using "mix-ins".

The add function we wrote in Python uses what I understand as "duck typing". If it quacks like a duck, walks like a duck, looks like a duck ... effectively, it's a duck. However, in this case, instead of talking about types that are "duck like", we're talking about types that are "addable". Thus, our add function in Python works on all types that are "addable" where being "addable" is implicitly defined as, "if add (+) works, it's addable". Note that Python is getting more elegant with respect to being able to define these "type classes" (i.e., kinds of types) through the introduction of Abstract Base Classes or ABCs (see PEP 3119).

Interestingly enough, the thought of having an add function that works on a class of types that are "addable" turns out to be a great first approach we can take for a Haskell implementation. Coincidence? Great minds think alike? You decide. Anyhow, here's how it's done in Haskell:

-- VersatileAdd.hs
{-# LANGUAGE TypeSynonymInstances #-}
class Addable a where
    add :: a -> a -> a

instance Addable Integer where
    add = (+)

instance Addable Double where
    add = (+)

instance Addable String where
    add = (++)
--------------------------------
Prelude> :l ./VersatileAdd.hs 
[1 of 1] Compiling Main             ( VersatileAdd.hs, interpreted )
Ok, modules loaded: Main.
*Main> add 3 4
7
*Main> add 3.0 4.0
7.0
*Main> add "I'm a " "String!"
"I'm a String!"

In the "VersatileAdd.hs" file, we define a "class of types" that are "addable" using the "class Addable a where ..." syntax. Note that we must use type variables (the "a" in "class Addable a where") in our type class definition since that is the whole point of type classes. We're saying, let's call this group of types Addable where some instance "a" has these properties. Note also that Haskell is fussy about case. Specific types (e.g., Double, Int, Integer, Float, Char) must start with an upper case letter. Type variables must be lower case. By convention, type variables are usually a single letter but they don't have to be.

What we have said with our definition of addable is that "to be addable, one must define the add function". This is essentially what we had (implicitly) in Python. The reason why we have to fuss with defining this where Python did not is that Python already had "+" defined for both addition and appending. As we will see, Haskell uses a different operator for appends (namely "++") and thus never tried to "mix up" (+) for add and (+) for append but c'est la vie. At any rate, trying to copy cool things in Python using Haskell (and vice verse) is what this blog's about so let's not bad mouth our nice challenge, right?

Essentially, what we are doing in our "VersatileAdd.hs" source file is allowing many different types (Int, Integer, Float, Double, String) to all use the same function name, add. Depending on the type that is used to call add, a different implementation of add may be called. This is polymorphism by type (I believe called "parametric polymorphism").

The specific implementations of the add functions by type are defined as "instance Addable XXX where" where the XXX is the specific type we are defining as part of the "group of types that are Addable". We only have to define the function add to be fully compliant with the Addable type-class (i.e., "class Addable").

I should mention the funny "{-# LANGUAGE TypeSynonymInstances #-}" bit at the top of our source file. This is called a pragma and is a special instruction to the GHC compiler that is used to overcome a deficiency in the Haskell98 specification. Unfortunately, this also means that our code will only compile using the GHC compiler although this isn't too much of a concern since GHC is the de facto standard (and I'm also hoping this issue is one that will be fixed in future versions of the Haskell language). I don't plan to go into the deficiencies here but for further discussion of why this pragma is needed, please check out "Real World Haskell" Chapter 6: Relaxing Some Restrictions on Typeclasses.

The definition of add for both Double and Integer use the point free style I spoke of in previous posts. As a reminder, we are saying that the function add is the same as the function (+). Note for strings, we present the (++) function. The (++) function is predefined and guess what it does?

(++) :: [a] -> [a] -> [a]

The append function (++) takes two lists and returns a third which is list two appended to list one.

So there you have it! We can also write a Python-like add in Haskell. But wait! What about the Python call shown here:

>>> add([1,2,3],[4,5,6])
[1,2,3,4,5,6]

Oops, we forgot to define our add function for lists of numbers. But no problem, we can update our Haskell add definition file:

-- VersatileAdd.hs
{-# LANGUAGE TypeSynonymInstances #-}
class Addable a where
    add :: a -> a -> a

type ListOfDouble = [Double]

type ListOfInteger = [Integer]

type ListOfInt = [Int]

instance Addable Integer where
    add = (+)

instance Addable Double where
    add = (+)

instance Addable ListOfDouble where
    add = (++)
    
instance Addable ListOfInteger where
    add = (++)
    
instance Addable ListOfInt where
    add = (++)

instance Addable String where
    add = (++)

Here, we defined new type synonyms (ListOfInteger and the like). We have to do this for the whole "type synonym instances" override to work (if we defined "instance Addable [Int] where ..." the compiler would bark at us).

But whoa is me! Things were starting to look all nice and clean in Haskell but now we're enabling TypeSynonymInstances pragmas and, even worse, having to change our code for each "addable" instance out there... This is easy enough for now but if we have to define a new instance of Addable for every type we ever define, that could be cumbersome! And what if we had a much more complicated class than Addable -- something with several function definitions??!! Furthermore, look at our add implementations! We are repeating the same exact code for types Double, Int, Integer, etc. And similarly for all the ListOfXXX and String types (i.e., array types) we are just repeating the same code! Ack! What to do? what to do...?

Well, here's my attempt at a little elegance:

-- ElegantAdd.hs
data Addable a b = N a | L [b] deriving (Show, Eq)

myadd :: (Num a) => (Addable a b) -> (Addable a b) -> (Addable a b)
myadd (N x) (N y)= N (x + y)
myadd (L xs) (L ys) = L (xs ++ ys)
---------------
*Main> :l ./ElegantAdd.hs
[1 of 1] Compiling Main             ( ElegantAdd.hs, interpreted )
Ok, modules loaded: Main.
*Main> myadd (N 3) (N 5)
N 8
*Main> myadd (L "I'm not a ") (L "Number!")
L "I'm not a Number!"
*Main> myadd (L [1, 2, 3, 4]) (L [5, 6, 7])
L [1,2,3,4,5,6,7]

Here, we've defined a new data type that is polymorphic and uses existing type classes (i.e., "types of numbers" and "lists of types"). An Addable data type can either be a number (type class "a") or a list (type class "b"). I use the two different type variables because types that can be a "type of list" don't have to always be numbers. Note that I don't actually enforce the fact that type variable "a" must be a "kind of number" until the definition of myadd. Unfortunately (or perhaps fortunately?), we do have to use the type constructors "N" and "L" but other than that, we've successfully combined "add as addition" and "add as append" functionality into one function called myadd. The use of the Num type class and the predefined list type "[a]" has saved us all the work of re-deriving myadd for each specific type we want to be "Addable". Huzza!