Haskell versus other programming languages

Martin Sulzmann

Haskell versus Go

Here’s some simple exercise. In math terms, we’d like to generate the following list of tuples:

{ (x1,...,xn) | xi in {0,1,2} )

for some positive number n.

Here’s the straightforward solution in Haskell.

genN n
 | n <= 1   = [[0],[1],[2]]
 | n > 1  = [ e : rs | rs <- genN (n-1), e <- [0,1,2] ]

Here’s a solution in Go

func genN(n int) [][]int {
    ls := []int{0, 1, 2}
    if n <= 1 {
        xss_1 := [][]int{}
        for _, e := range ls {
            xss_1 = append(xss_1, []int{e})
        }
        return xss_1
    }
    xss_n_1 := genN(n - 1)
    xss_n := [][]int{}
    for _, xs := range xss_n_1 {
        for _, e := range ls {
            ys := append(xs, e)
            xss_n = append(xss_n, ys)
        }
    }
    return xss_n
}

Some runnable Go code to play around.

Demo where we run the Haskell and Go code. For certain n’s the Go code does not produce the correct output. Why

Haskell versus Go (cont’d)

We explain why there’s difference between Haskell and Go.

Recall the Haskell code.

genN n
 | n <= 1   = [[0],[1],[2]]
 | n > 1  = [ e : rs | rs <- genN (n-1), e <- [0,1,2] ]

Haskell programmers can focus on solving the problem and do not need to worry about the underlying operational semantics.

Recall the Go code.

func genN(n int) [][]int {
    ls := []int{0, 1, 2}
    if n <= 1 {
        xss_1 := [][]int{}
        for _, e := range ls {
            xss_1 = append(xss_1, []int{e})
        }
        return xss_1
    }
    xss_n_1 := genN(n - 1)
    xss_n := [][]int{}
    for _, xs := range xss_n_1 {
        for _, e := range ls {
            ys := append(xs, e)
            xss_n = append(xss_n, ys)
        }
    }
    return xss_n
}

Go slices are represented as

If appending an element to a slice execeeds the capacity, a new array of sufficient size will be allocated.

For efficiency reasons, when assigning a slice to a new variable we copy references (to the array) rather then duplicate the slice including the underlying array.

This means that in case of

ys := append(xs, e)

slice ys and slice xs might share the same underlying array. This then leads to unexpected, indeterministic behavior.

The (Go) fix is to create a new slice.

ys := append([]int{}, xs...)
ys = append(ys, e)

Summary

We have seen:

Copying algorithms between languages is not syntax translation..

Haskell gives us:

Go gives us:

One optimizes for reasoning clarity. One optimizes for pragmatic systems programming. Neither is “better”. They optimize for different constraints.

Haskell versus Java

We show how to model OO in Haskell by making using of a combination of

As a running example we consider geometric objects.

Geometric objects in Haskell

Some data types.

data Square = Square Int

data Rectangle = Rec { len :: Int, width :: Int }

Some type classes to describe the behavior.

class Shape a where
   area :: a -> Int

instance Shape Square where
  area (Square x)    = x * x

instance Shape Rectangle where
  area r    = len r * width r

class (Show a, Shape a) => ShapeExt a where
   scale :: a -> Int -> a


instance ShapeExt Square where
  scale (Square x) s = Square (x * s)

instance ShapeExt Rectangle where
  scale r s = Rec { len = len r * s, width = width r * s }

instance Show Square where
  show (Square x) = "square(" ++ show x ++ ")"

instance Show Rectangle where
  show  (Rec {len = l, width = w }) = "rectangle(" ++ show l ++ "," ++ show w ++ ")"

Can we store two geometric objects in a list?

The following will not type check.

r = Rec { width = 2, len = 3 }
s = Square 4

ls = [r, s]

Here’s the type error message.

    • Couldn't match expected type ‘Rectangle’
                  with actual type ‘Square’
    • In the expression: s
      In the expression: [r, s]
      In an equation for ‘ls’: ls = [r, s]

Abstract representation for geometric objects

data GeoShape = forall a. ShapeExt a => MkGeoShape a

The above data type declaration makes use of existential data types in combination with a type class. Why existential? There seems to be a universal (for all) quantor in the above definition? Yes, we universally quantify over a but this type is not part of the return type. Hence, the following logical equivalence

forall a. (I implies J)        =     (exists a. I) implies J

where J does not refer to a

which justifies the name existential data type.

In more detail, the constructor MkGeoShape has the following type.

MkGeoShape :: ShapeExt a => a -> GeoShape

The argument of the constructor is any value of type a that is an instance of the ShapeExt type class.

The following type checks.

s1 :: GeoShape
s1 = MkGeoShape r

s2 :: GeoShape
s2 = MkGeoShape s

shapes = [s1, s2, MkGeoShape r2]

By embedding square and rectangle into the new type GeoShape, we can store both in a list.

What can do with elements of this list? We can apply all the operations that are available for geometric objects by lifting them to GeoShape.

instance Show GeoShape where
    show (MkGeoShape x)    = show x

instance Shape GeoShape where
    area (MkGeoShape x)    = area x

instance ShapeExt GeoShape where
    scale (MkGeoShape x) s =  MkGeoShape (scale x s)

Here is an example.

ex2 = putStrLn (unlines (["Sum of the area of"] ++
                         map show shapes ++
                         [show (sum (map area shapes))]))

Here’s the complete runnable Haskell code.

Summary