Lists

The third section of chapter one covered some basic functional programming concepts. Namely Cons lists, their mirror Snoc lists, and the functions built to operate on them. Particularly the adaptations of the foldn function from the previous section which operated over Nat.

data Listl a = Nil | Snoc (Listl a, a) deriving Show
data Listr a = Empty | Cons (a, Listr a) deriving Show 

foldl' c h Nil = c
foldl' c h (Snoc (x, a)) = h (foldl' c h x) a

foldr' c h Empty = c
foldr' c h (Cons (a, x)) = h a $ foldr' c h x

As you can see in the definition of both Cons and Snoc they are identical to the previous sections definition of natural numbers save for an addition bit of information, whatever you are storing in your list. Also, Cons and Snoc are only different in the position of their recursive self reference. It’s only the general understanding of the position by those using the type and the functions created for them ( : as an example ) that makes it behave the way it does. If you were, without prior knowledge, to examine the types by themselves it wouldn’t be clear that they were operated upon in significantly different ways when adding new elements (other than the difference in the names of the data constructor). As an example we could redefine the haskell infix cons operator to work with Snoc lists just as it would a Cons list (Note: I’ve been informed that in practice this isn’t possible, but the purpose of the example still holds).

data Listl a = Nil | Snoc (Listl a, a) deriving Show

(:) :: a -> Listl a -> Listl a
x : y = Snoc (y, x) 

example = 1 : Snoc(Snoc(Nil, 3), 2)
          --  Cons(2, Cons(1, Nil)) would be the norm

Also of interest in this chapter is the myriad of operations that can be defined in terms of foldr for Cons lists and foldl for Snoc lists, much as with Nat. From two of the excercises:

--Excercise 1.7
convert :: Listl a -> Listr a
convert = foldl' Empty h
    where h x y = Cons(y, x)

--Excercise 1.8
catconv :: Listl a -> Listr a -> Listr a
catconv m n = foldl' n h m
    where h x y = Cons(y, x)

Or a quick implementation of map’ for Cons lists built atop our extremely reusable foldr’

map' f = foldr' Empty h
    where h x y = Cons (f x, y)

-- > map' (+2) $ Cons (1, Cons(2, Empty))
-- Cons (3,Cons (4,Empty))

Further Work

I’m getting a lot of joy from rehashing these basic data structures and the implications of understanding them at a relatively low level are obvious. Lists make up such a huge portion of the programming that we do and understanding the types of lists that make the most sense for use within code for both comprehension and performance can provide real value. Also, in fooling around with some little coding challenges on the side (examples to be posted soon I hope) in haskell I’ve noticed my ease with maps and folds becoming greater.

One bit that I have to revisit is the proof from the middle of the section that the ++ operation is associative and that nil is the left and right unit. I was never very good with proofs, I’ve long since lost the terminology, and I would like to complete the exercise that requires that knowledge.