foldr the magic function

20 11 2007

Recursion

In Haskell we essentially use recursion, this mean defining a function using itself definition.
A recursive function is, for example the factorial:

in haskell we define it like that:

fact 0 = 1
fact n = n * fact (n-1)

As you can see Haskell is authentic mathematic, pure functional language.

My point here is to show you the magic of the function foldr in Haskell, so I will assume that you already know Haskell, and maybe are accustomed to use foldr function.

ok…

Seeing the magic

The definition of the function length could be something like this:

length [] = 0
length (h:t) = 1 + length t

The definition of the function sum could be something like this:

sum [] = 0
sum (h:t) = h + sum t

And the definition of the function mult could be something like this:

mult [] = 1
mult (h:t) = h * mult t

As you can see in all three definitions we have a pattern and we can generalize it:

functionName [] = stopCase
functionName (h:t) = constant operator (functionName t)

We always need the stopping case of the function!

And the same happens in other functions like reverse:

reverse [] = []
reverse (h:t) = reverse t ++ [h]

In this case we have:

functionName [] = stopCase
functionName (h:t) = (functionName t) operator constant

So, we will always use the function applied to the tail of the list!

If we use some of lambda notation we can see one more pattern, the real one:

sum [] = 0
sum (h:t) = (a b -> a + b) h (sum t)

reverse [] = []
reverse (h:t) = (a b -> b ++ [a]) h (reverse t)

Our lambdas functions have arity 2, because those are the parts in which we can see the lists (head + tail).

Now we can generalize even more, considering function have arity 2:

functionName [] = stopCase
functionName (h:t) = function h (functionName t)

well, that’s not right for Haskell. Because it doesn’t know what function represents, that’s because the definition of functionName doesn’t receive that argument. And the same happens with stopCase.

functionName function stopCase [] = stopCase
functionName function stopCase (h:t)
     = function h (functionName function stopCase t)

Et voilá.

In fact the last definition is the true one for foldr. Easy right?

Functions with foldr’s

Well… Now we can redefine previous functions just with foldr’s:

length l = foldr (a b -> 1 + b) 0 l
sum l = foldr (+) 0 l
mult l = foldr (*) 1 l
reverse l = foldr (a b -> b ++ [a]) [] l

And all the functions over list’s…

and l = foldr (&&) True l
or l = foldr (||) False l

More magic

Foldr is more magical than this, it is one catamorphism! A Catamorphism over this data type:

data [a] = [] | a : [a]

Haskell List’s!

That means that foldr functions “knows” the recursive pattern over List’s.

Foldr also allows you to use Pointfree notation, witch I like. Formal explanation.

length = foldr (a b -> 1 + b) 0

More foldr’s

We can also write foldr’s functions to every data type that we create, and “explain” how recursive patterns works for our new data type:

data BTree a where
    Empty :: BTree a
    Node :: a -> BTree a -> BTree a -> BTree a

foldrBTree :: (a -> b -> b -> b) -> b -> BTree a -> b
foldrBTree op k Empty = k
foldrBTree op k (Node a l r) = op a (foldrBTree op k l) (foldrBTree op k r)

Now if we have a Binary Tree and want to know how many nodes it has, we just have to do this:

countNodes = foldrBTree (\a nodesLeft nodesRight ->a+nodesLeft+nodesRight) 0

If we want to know how many Empty’s our tree has:

countEmpty = foldrBTree (\_ nodesLeft nodesRight -> nodesLeft + nodesRight) 1

and so on…

Fold’s are really a genuine help for your code.
Later on I will talk more about catamorphisms…

Advertisements




Haskell history

27 10 2007

Haskell is so far one of my favorite programming languages, I don’t know if you noticed (lolz). Because it is ease of proof, no side effects, strongly typed, polymorphic, powerful, elegant and so much more.

Yesterday I was searching if there were any report talking about Haskell authors, other than Simon Peyton Jones or Paul Hudak. What I found out much more than I expected. I’ve found the History of Haskell paper. The paper that was published at 3rd History of Programming Language Conference in June 2007.

I start reading immediately, it was fascinating… The paper is a bit long (55 pages in two columns style), but deserves attention. The history is told for those who made History, Simon Peyton Jones, Paul Hudak, John Hughes and Philip Wadler, the main authors.

Haskell principles, ideology, implementations, tools – Haskell world, are in this paper. This document is excellent for those who want to learn Haskell or just know it history.

References:

Haskell Wikipedia entrance

IFIP WG 2.8





Hterogeneous lists in Haskell

11 10 2007

Sometime ago I needed something that Haskell don’t have by default: heterogeneous lists…

After think about that I decide to make my own “module” so I did this:

data Hetero where
        H :: forall a . Show a => a -> Hetero
instance Show Hetero where
        show (H s) = show s

In fact is just a data type and an instance to show the data. Nothing more, nothing less…

Here some examples of heterogeneous lists:

list , list2 :: [Hetero]
list = [H ['a'..'z'], H 10, H '0', H 3.1, H [1..10]]
list2 = [H [H [H '0', H [1..10]], H '0'], H 1]

By the way, the data type is write using Generalised Algebraic Data-Types (GADT). GADT is, in fact a very recent thing in Haskell, I will talk about that latter.

Some time ago, after doing this, I was searching GADT and find this after I find another one talking about forall's and exists in Haskell, in that one, on the first example you can learn more about Heterogeneous Lists in Haskell and Haskell…

NOTE: Today I preferred blue.

code here