Algebra of Programming: Chapter 1 Section 3
ListsThe 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))