Recreating the Haskell List Part 1

This is part 1 of a 6 part tutorial

Data Structures as Containers

In a language like C, you can think of data structures as containers which hold one or more objects.

A Container

typedef struct int_container_t {
    int i;
} int_container_t;

The int_container_t type is now something which holds one int. To make the same sort of data structure in Haskell you would write:

Int container in Haskell

data IntContainer = IntContainer Int deriving Show

Ignoring for a moment the suffix deriving Show, this looks a lot like a function declaration, because that is essentially what it is. The identifier IntContainer appears on both sides, but the two are actually in two different namespaces. It is not necessary for these two identifiers to have the same name, but people will often do this by convention.

The left hand side of this declaration names a new type IntContainer, and the right hand side is defining a data constructor for this type, essentially a function named IntContainer which takes one Int as argument which it uses to create an instance of this type.

Using the data constructor in ghci

--  create an instance of IntContainer passing the value 4
IntContainer 4
=> IntContainer 4
--  Checking the type signature of the IntContainer data constructor function
:t IntContainer
=> IntContainer :: Int -> IntContainer
--  checking the type of an instantiated IntContainer
let i = IntContainer 4
:t i
=> i :: IntContainer

If I pass the data constructor a 4, it returns something which is of type IntContainer. The ghci command :t can be used to get type information about just about anything in Haskell. IntContainer :: Int -> IntContainer is read “IntContainer is a function which accepts an Int and returns an IntContainer”. i :: IntContainer is read “i is of type IntContainer”.

Algebraic Type System

In C++, we have a template system which allows us to create classes and methods where the types involved are variable. If we wanted to create a Container class in C++ which could hold not only an int but any type, we could write a class like this:

C++ Templated Container

template <class T>
class Container {
    T _value;
    public:
    Container(T value) : _value(value) {}
};
Container<int> container = Container<int>(4);

Haskell has an algebraic type system which enables us to do what C++ does with its template system, but is far easier to use and debug. Much of the simplicity comes from the lack of pointers in Haskell, and the fact that compound types and functions are treated the same as primitives without needing to put much thought into copy constructors and memory management.

Haskell container which can contain any type

data Container t = Container t driving Show
--  ghci output
Container 5
=>  Container 5
Container 4.2
=> Container 4.2
Container "String"
=> Container "String"
Container [1,2,3]
=> Container [1,2,3]
let x = Container (\x -> x + 1)
:t x
=> x :: Container (Integer -> Integer)
x
  <interactive>:1:0:
      No instance for (Show (Integer -> Integer))
      arising from a use of `print' at <interactive>:1:0
      Possible fix:
      add an instance declaration for (Show (Integer -> Integer))
      In a stmt of a 'do' expression: print it

This time, the left hand side of the type declaration is parameterized with a variable type t, whereas in IntContainer it did not. A type variable like t is a placeholder for a type, so on the right hand side t can be replaced by any type, for example when you pass the data constructor a String, it is as if you had declared data Container = Container String deriving Show. In all, so far this is very much like C++ templates.

In the above example it is shown this works with Int, Float, String, or even [Int] (a list of Ints). It will even accept another function, as shown as I pass it the lambda (\x -> x + 1), because a function is a typed value just like anything else. This creates a value with the type signature x :: Container (Integer -> Integer) meaning “x is a container holding a function which accepts an Integer and returns an Integer”.

Everything works fine until I type x and ghci’s read eval print loop tries to print a the function (x -> x + 1). The other data types like Int and String have properly defined Show functions already, but a lambda does not have any meaningful way to display itself. I have told Container to derive its show function where it is possible, but it was not possible when passed a lambda function, therefore we got an error.

Typeclasses in Haskell

A class in Haskell is not quite the same as in object oriented programming languages. To define a class you essentially define only an interface, and it is not necessary to provide any implementation. Any type can be a member of a class if it declares that it supports the class’s interface.

Let’s define a funny example class:

Defining a class

class PikachuShow a where
  pikaShow :: a -> String
--  Make Container an instance of PikaShow
instance PikachuShow (Container t) where
  pikaShow _ = "Pika Pika!"
let x = Container 1
x
=> Container 1
=> show x
Container 1
pikaShow x
=> "Pika Pika"

Now Container is an instance of Show and PikachuShow.

Container derives its show function from its data members such as String or Integer which are instances of Show. (Integer -> Integer) is not an instance of Show and container cannot find a show implementation for it. Container is an instance of PikachuShow and has therefore implemented the pikaShow function

The pikaShow function ignores its argument, because of the _ in the function argument list, this is also seen in languages such as Erlang, and to some extent in Ruby. The argument, if you had bound it to a variable, would be the Container it was called with.