Counting Cats and Listing Snakes

In today's installment, I thought I'd explore how Haskell lists would look if they were implemented in Python. Per the spirit of this blog, it's my intention to take ideas in Haskell and put them in Python and vice verse in an attempt to better understand functional programming.

Python has a lot of nice tools for the functional programming paradigm -- there's a nice overview from A.M. Kuchling on the Python website here. I'm curious if Haskell enthusiasts reading this functional programming overview experience a few "cringe points" (I did). Even so, all-in-all I thought this is a very nice document showing the power of Python to implement programs in the functional style. That being said, there's definitely a "middle-path" feel to Python where pure functional or object-oriented concepts are sacrificed in the name of "the greater good" (i.e., clarity and practicality). This is perhaps why Python is so successful -- it takes the middle path...

But anyhow, back to the task at hand: how would Haskell linked lists look if implemented in Python? Also, a few posts back, I explored how one could combine "add as addition" (Haskell operator "+") and "add as append" (Haskell operator "++") into one function in Haskell (similar to how Python uses the "+" operator for numbers and for lists, respectively). However, we never did the reverse for Python. If we implemented our own custom numbers and lists in Python and then wanted to implement "add as addition" for numbers and "add as append" for lists both using the (+) operator, what would this look like? Note that this is what the "+" operator does normally in Python. It would be even nice to define the Haskell "+" and "++" in Python but unfortunately, we can't define a "++" operator in Python to my knowledge.

OK, so let's define some number type, Num, that we can perform addition with:

class Num:
"""A number"""
def __init__(self, val):
self._val = val

def __add__(self, other):
return Num(self._val + other._val)

def __str__(self):
return str(self._val)

The method "__add__" is a convention in Python that gets called when "+" is applied to an instance of the user-defined type (a.k.a., class) defining it. In our case, we'll only be adding Nums to each other so I won't worry about type conversion, mixing numerical types, etc. Similarly, the "__str__" function is called when str(inst) is called where inst is an instance of the user-defined type that defines the __str__ method.

We can exercise instances of the Num type as follows:

n1 = Num(1)
n2 = Num(2)
n3 = n1 + n2
print(n3)
#---------
# => 3

Now to the linked list. Let's consider that we have a list of instances of type Cat (yup, you heard me right. We're talking about our cute furry friends with whiskers). A linked list is a data structure that holds a reference to the head of the list and the tail of the list which itself is a list -- the rest of the cats (i.e., the whole kit and caboodle).

We will signify that we're at the end of our list by using Python's built in instance, None (an instance of NoneType).

class LinkedList:
"""A list"""
def __init__(self, head, tail):
self._head = head
self._tail = tail or None

def __add__(self, other):
"""Addition as appending"""
if self._tail is not None:
return LinkedList(self.head(), 
LinkedList(self._tail.head(),
self._tail.tail()) + other)
else:
return LinkedList(self._head, other)

def head(self):
return self._head

def tail(self):
return self._tail

def __str__(self):
return "%s:%s"%(str(self._head), str(self._tail))

def __len__(self):
if self._head is not None:
if self._tail is not None:
return 1 + len(
LinkedList(self._tail.head(), self._tail.tail()))
else:
return 1
else:
return 0

The "tail or None" bit in the code above can be thought of as an application of the "or" function. If tail comes in as something that evaluates to false (like "[]", the empty list), we're going to use "None" instead. I could have used "[]" instead of "None", I just need to be consistent to identify the end of the list. (Note that we can get tripped up here if someone threw in "False" for example. This code is not meant to be production, just a learning exercise).

For convenience, we'll define a function, listToLinkedList, that takes a Python list and returns an instance of type LinkedList.

def listToLinkedList(lst):
"""Takes a Python indexable object to a List object"""
if len(lst) > 0:
return LinkedList(lst[0], listToLinkedList(lst[1:]))
else:
return None

And just so we have something interesting to list, let's define a new user defined type -- cats!

class Cat:
def __init__(self, name):
self.name = name

def __str__(self):
return "Cat %s"%repr(self.name)

def __repr__(self):
return "Cat(%s)"%repr(self.name)

The __repr__ is a special function (called with repr(instance)) that returns the string representation of an object. The string function is meant to be human readable while the repr function is more machine readable. If you'd like to read more about it, check the Python docs here.

And now to exercise the code:

listOfCatsOne = listToLinkedList([Cat("Mittens"), Cat("Nippers"), Cat("Bob")])
print(listOfCatsOne)
# => Cat 'Mittens':Cat 'Nippers':Cat 'Bob':None

I've also implemented a LinkedList function, len, to count the number of members of the list. This is created via recursion.

Let's exercise it:

print("There are %d cats in list one\n"%len(listOfCatsOne))
# =>
# There are 3 cats in list one

Let's say we have a list of three kittens (Mittens, Nippers, and Bob) and we want three more cats (O'Mally, Nosey, and Fuzzbee) to join them at the end of the line (i.e., we want to append the LinkedList of O'Mally and others to the end of the LinkedList of Mittens and others). This will look as follows:



So in the upper part of the image, we can see the structure of a linked list. A linked list consists of a head containing Mittens and a tail consisting of the linked-list with a head of Nippers and a tail consisting of a linked-list with a head of Bob and a tail consisting of the empty list. The "empty list" is a special flag of sorts that lets us know the end of the list has been reached. Cool, huh?

When we append lists (show at the bottom part of the figure), we create a new list structure consisting of each element of the original list successively appended until we hit the end of list one (i.e., the empty list) and in place of the "empty list" we pop in the second list (which ends in an "empty list").

And the code:

listOfCatsTwo = listToLinkedList([Cat("O'Mally"), Cat("Nosey"), Cat("Fuzzbee")])
listOfCatsThree = listOfCatsOne + listOfCatsTwo
print(listOfCatsThree)
# =>
# Cat 'Mittens':Cat 'Nippers':Cat 'Bob':Cat "O'Mally":Cat 'Nosey':Cat 'Fuzzbee':None

Yippee! So now we can append lists of cats to each other and count them up! In Haskell, we can create our own linked list type to demonstrate the same effect.

#!/opt/local/bin/runhaskell
module LinkedList where

import Text.Printf (printf)

type Name = String

data Cat = Cat Name

data List a = Cons a (List a) | Nil

instance Show Cat where
show (Cat n) = "Cat " ++ (show n)

instance (Show a) => Show (List a) where
show (Cons x xs) = (show x) ++ ":" ++ (show xs)
show Nil = "[]"

(+++) :: (List a) -> (List a) -> (List a)
(+++) Nil ys = ys
(+++) (Cons x Nil) ys = Cons x ys
(+++) (Cons x1 (Cons x2 xs)) ys = Cons x1 $ (Cons x2 xs) +++ ys

len :: (List a) -> Int
len Nil = 0
len (Cons x xs) = 1 + len xs

main :: IO ()
main = do
let catListOne = Cons (Cat "Mittens") $ Cons (Cat "Nippers") $ Cons (Cat "Bob") Nil
let catListTwo = Cons (Cat "O'Mally") $ Cons (Cat "Nosey") $ Cons (Cat "Fuzzbee") Nil
print (catListOne +++ catListTwo)
printf "There are %d cats in list one\n" (len catListOne)
-- =>
-- Cat "Mittens":Cat "Nippers":Cat "Bob":Cat "O'Mally":Cat "Nosey":Cat "Fuzzbee":[]
-- There are 3 cats in list one

As you can see, we get the same result. Note that all of this functionality is built into Haskell and could be written in a more concise format:

main2 :: IO ()
main2 = do
let catListOne = [Cat "Mittens", Cat "Nippers", Cat "Bob"]
let catListTwo = [Cat "O'Mally", Cat "Nosey", Cat "Fuzzbee"]
print (catListOne ++ catListTwo)
printf "There are %d cats in list one" (length catListOne)
-- =>
-- [Cat "Mittens",Cat "Nippers",Cat "Bob",Cat "O'Mally",Cat "Nosey",Cat "Fuzzbee"]
-- There are 3 cats in list one

Similarly, the append function of Python is also pre-defined and could have been written as:

listOfCatsFour = (Cat("Mittens"), Cat("Nippers"), Cat("Bob"))
listOfCatsFive = (Cat("O'Mally"), Cat("Nosey"), Cat("Fuzzbee"))
print(listOfCatsFour + listOfCatsFive)
print("There are %d cats in lists four and five"%(len(listOfCatsFour + listOfCatsFive)))
# =>
# (Cat('Mittens'), Cat('Nippers'), Cat('Bob'), Cat("O'Mally"), Cat('Nosey'), Cat('Fuzzbee'))
# There are 6 cats in lists four and five

So to summarize, as a means of better understanding Haskell's lists, I've implemented them in Python (with cats!) as well as (re-)implemented them in Haskell (with more cats!). So what have we learned? First, everything is better with cats!

But seriously, this exercise was aimed at bringing more clarity to what Haskell LinkedLists do. Since Python is easy to read and understand, re-writing Haskell in Python can sometimes bring further clarity to what's going on (at least if you come from an imperative programming language background like me). So for what it's worth, there it is! Meow!