I’m proud to announce the first release of my lhs2TeX-hl tool. For us who fancy using colours in our presentations or papers this should now go a whole lot easier. Go to the lhs2TeX-hl homepage!

Install it like this:

[bash]
> cabal install lhs2TeX-hl
[/bash]

lhs2TeX-hl is run before you run lhs2TeX and you supply it with the input file and the output file. A typical execution would look like this:

After some time of struggling with MacFuse (+MacFusion) and SSHFS I set out to get something that works nice, is integrated in OS X nicely and above all, is not sslooow. AFP which is all of this is available for Debian but without support of the new encrypted password mechanism.

Apparently is was there when I tried this the last time and I missed it. But now it works. This works seamlessly with OS X 10.6. I now even have a nice heavy duty server icon in the Finder for my Debian machine. This is because of the avahi service.

This how to also explains how to setup your TimeMachine to backup to the Debian server.

Currently there is no package for the Haskell-Platform in Debian stable. However, the source of this platform and GHC is available for download at ghc and platform.

However, there are some issues to solve when installing the platform from source. Mainly you’ll be missing several packages. The following commands worked at my own Debian machine. If you find out that’s something is missing that was apparently already installed on my machine, don’t hesitate to leave a comment.

The following commands are all executed as root.
First we need to download the sources, I’m using the x86 sources, but feel free to use the x64 version:
[bash]
cd /tmp
wget http://www.haskell.org/ghc/dist/6.10.4/ghc-6.10.4-i386-unknown-linux-n.tar.bz2
wget http://hackage.haskell.org/platform/2009.2.0.2/haskell-platform-2009.2.0.2.tar.gz
[/bash]

Now we need to extract these sources:

[bash]
tar xvf ghc-6.10.4-i386-unknown-linux-n.tar.bz2
tar xvzf haskell-platform-2009.2.0.2.tar.gz
[/bash]

Before we do any other stuff, let’s ensure that we have all the packages and libraries we need before continuing.

Also make sure that you apply this patch to the platform, the bug has been around for some time now but hasn’t been fixed apparently, it can be found at bug #84:

+# Is this exact version of the package already installed?
+is_pkg_installed () {
+ PKG_VER=$1
+ grep ” ${PKG_VER} ” installed.packages > /dev/null 2>&1
+}
+
# Actually do something!
cd packages
for pkg in cat platform.packages; do
- cd “${pkg}” || die “The directory for the component ${PKG} is missing”
- echo “Installing ${pkg}…”
- install_pkg ${pkg}
- cd ..
+ if is_pkg_installed “${pkg}”; then
+ echo “Platform package ${pkg} is already installed. Skipping…”
+ else
+ cd “${pkg}” || die “The directory for the component ${PKG} is missing”
+ echo “Installing ${pkg}…”
+ install_pkg ${pkg}
+ cd ..
+ fi
done

echo
[/bash]

Now go to the ghc dir and build it.

[bash]
cd ghc-6.10.4
./configure
make install
[/bash]

And if all of this goes well you can now go to the haskell-platform dir and install it:

[bash]
cd ../haskell-platform-2009.2.0.2/
./configure
make
make install
[/bash]

Non-mutually recursive and Mutually recursive datatypes

Welcome back. In this post we will look at creating type algebra’s and folds for more complicated data types. In essence, this exercise will not be any more difficult than the previous ones, provided that you stick with the steps. Up in this part, are the non-mutually recursive datatypes and mutually recursive datatypes.

First up, data structures that are recursive into other data structures. The folds for these data structures are no more complex than their `simpler’ forms. In fact, you could treat them the same, but for clarity we will treat them as distinct. If you want to know more about the previous part, it might help your search if you look for the keyword catamorphism.

Non-mutually recursive datastructures

Look at the following data structure. It’s data constructors refer both back to the data structure itself and to another data structure. The other data structure has no reference back to this structure. This kind of data structures are quite common.

[haskell]
data MaybeTree a = Node (Maybe a) (MaybeTree a) (MaybeTree a)
| Leaf (Maybe a)
– This one is already defined in the prelude
data Maybe a = Just a | Nothing
[/haskell]

Recall that in our previous folds and algebras we choose to replace our self-recursive types with a free variable r. In this case we also have a reference to another data structure, namely Maybe a. We will denote this by using another free variable, lets say m.

[haskell]
type MaybeTreeAlgebra a m r = ( ( m -> r -> r -> r – Node
, m -> r – Leaf
)
, ( a -> m – Just
, m – Nothing
)
)
[/haskell]

Notice that we’ve split up the the functions for each data type in separate tuples. This is to make the algebra somewhat more readable. It has one disadvantage though which we’ll see later on.

We obtained this algebra by methodically looking at the types of the constructor functions and replacing any recursive types by their free variable counterparts, r for MaybeTree a and m for Maybe a.

Now we are going to construct the fold function. We will be doing this in exactly the same way as we did with all previous folds.

Determine which datatypes are used (previously there was only one); This step is very simple if you already have the algebra.

for each of these datatypes exhaustively define a fold function;

look at the result.

Following these steps again gives us the fold on our datatype. Please convince yourself that this is the case by defining foldMaybeTree yourself.

If we do it exactly as described above it will provide us with the following fold. Notice that we gave meaningful names to every replacement function stating the datatype they are intended for. Except for the top level function which we called f. This is because writing out the whole name for that function everywhere would be to much of a hassle and if you use f for this way it will be quite clear in time.

[haskell]
foldMaybeTree’ :: MaybeTreeAlgebra a m r -> MaybeTree a -> r
foldMaybeTree’ ((node, leaf), (just, nothing)) = f
where f (Node x l r) = node (maybe x) (f l) (f r)
f (Leaf x) = leaf (maybe x)
maybe (Just x) = just x
maybe (Nothing) = nothing
[/haskell]

Notice that we are using a datatype here that is already defined in the prelude. It would be wise to check whether someone didn’t already provide a fold function for our little datatype Maybe a. Because that’s we essentially did, we inlined the fold for Maybe a inside our fold for MaybeTree a. Obviously this isn’t a problem if you are sure that your datatype will stay `contained in’ in your datatype.

So we see that it is prudent to check for already existing folds if we use already existing datatypes. And it turns out that there already is a fold for Maybe a, namely maybe.

[haskell]
maybe :: b -> (a -> b) -> Maybe a -> b
maybe n _ Nothing = n
maybe _ f (Just x) = f x
[/haskell]

So lets refine our little procedure to determine the fold of a datatype:

Determine which datatypes are used (previously there was only one); This step is very simple if you already have the algebra.

for each of these datatypes exhaustively define a fold function or check whether such a fold function already exists;

look at the result.

If we now use this knowledge our fold function can be written as follows:

[haskell]
foldMaybeTree :: MaybeTreeAlgebra a m r -> MaybeTree a -> r
foldMaybeTree ((node, leaf), (just, nothing)) = f
where f (Node x l r) = node (fmaybe x) (f l) (f r)
f (Leaf x) = leaf (fmaybe x)
fmaybe = maybe nothing just
[/haskell]

We’ve seen how to use algebra’s but we haven’t seen a step by step procedure for creating one. So let’s add that to our procedure for creating our own folds. In our order to create the algebras as we’ve seen them here, with tupled functions you can follow this procedure:

For each data constructor in your datatype: create a function that takes the same parameters as the constructor function and replace every occurrence of a reference to one of your datatypes with a unique type variable (two occurrences to the same type should get the same variable). These functions should be grouped in tuples by their datatype. Do not forget to name all the type variables in the left-hand side of the type definition.

Normally this error would mean that you have some weird syntax error somewhere in your yml files. However, if you are sure everything is up to spec be sure to check whether there are any `hidden’ files in the folder. Such files start with a dot and are also read and parsed by the command line generator.

This could potentially fail, in case you get the aforementioned error. Be sure to remove these files before proceeding. To check whether there are any, go to the directory and retrieve it’s listing.

[bash]
cd /some/path/to/your/yml/files
ls -lha
[/bash]

If you see any files starting with a dot and ending in .yml be sure to check them for any valuable content and throw them away.

Thanks to rajat pandit for hinting to this solution.

Welcome to this little explanation on how to determine the fold of a Haskell
datatype. First we’ll look at how we define functions over lists, something
everyone starting with Haskell should be sufficiently familiar with, after which
we move on to the datatypes. You’ll see different ways how to calculate the sum
of a list, how to fold over a list, what datatypes are and, how to fold over a
datatype, specifically the BinTree a datatype. Most importantly, I hope you
will grow to understand what a fold is, and why they are so important and useful
when programming Haskell.

During our functional programming course at Utrecht University I noticed
students having anxiety of datatypes and even more for folds. Not because they
couldn’t grasp the workings of a single example but more a lack of a view on the
complete picture and lack of experience with the Haskell datatype way.

So, what are datatypes? Datatypes are a way of notating the abstract structure
of your data. There are several datastructures known to man, such as lists and
trees.

Lists

Lists in Haskell are used in several ways. Today we will look at how to
calculate the sum of a list. Intuitively you calculate the sum of a list by
adding its elements together. Starting with the first element and then
continuing on to the rest. This is how we literally translate that thought into
Haskell code:

1234

sum::[Int]->Intsum[]=0sum(x:xs)=x+sumxs-- sum [1..4] = 10

Would we be calculating the product of the list, we’d do the same except we
multiply instead of adding.

Looking at these two examples we can see that we have two similarities. We
always have recursion on the tail of the list and we do something with the head
of the list and the result of the recursion. In the first example we add them
together, and in product we multiply them. Another property of most functions
over lists is that there is a base case for the empty list. We call this the
identity of our function, sometimes also referred to as unit.
The identity of addition is 0 and the identity of multiplication is 1.

Now we look at one of the folds over lists defined in the prelude,
foldr. Make sure you know what each parameter stands for.
Note: There are some downsides to this function, mostly that it
will not work for large lists, you’ll see more on this later.

12345

foldr::(a->b->b)->b->[a]->bfoldrfz[]=zfoldrfz(x:xs)=fx(foldrfzxs)-- The line above can also be written as:-- foldr f z (x:xs) = x `f` (foldr f z xs)

Now, take a moment to let this function soak in and try to think of how you
would define sum and product in terms of this
foldr. Crucial at this point is to notice that we do not see any
type hardcoded in the type of foldr It may be helpful to look at
this fold, which is the identity function for lists:

If we look at our sum function, the operator between each recursive call is
(+) and our base case is 0. So that’s what we are going to use for
our sum in terms of foldr.

Thus far we only have lists of Int for our examples. However, for
sake of usability we will now move on to lists of numeric elements. Because
(+) is defined for all numbers. (If you wish to read more on this
subject please look up classes and instances.) Notice how the type of sumList
changes while it’s definition remains unaltered.

12

sumList::Numa=>[a]->asumListlist=foldr(+)0list

Now that we have seen how we can determine the function and identity for our
fold from our recursive function to a definition in terms of foldr.
And most importantly, the foldr takes care of the recursive nature of the list
for us and the only thing it asks us in return for that is an operator and an
identity for your operation. So the fold can now be used to define several
operations on lists.

I told you about a problem of foldr. Depending on the size of your
list the above sumList may not work. Try the following on your
machine:

First, let’s take a look at how data structures in Haskell can be defined. In
short we have the data keyword, followed by zero or more type
variables, a = and then a number of data
constructors separated by a |.

Now that you have familiarized yourself with lists we can proceed to a slightly
more complicated datastructure. The Tree. In this example we will use a simple
binary tree. A binary tree can be denoted as follows:

In this case BinTree is the type constructor and
Node and Leaf the data data constructors.

Remember that the goal of folds is to separate the implementation of the
recursion from the actual operation we want to execute on the datatype. So we
have one function, the fold, that takes care of the recursion and
several other functions that use this fold to specify certain semantics on the
datatype. We are going to calculate the sum of all elements in this tree.

The above binary tree has elements in the nodes and nothing in the leaves. You
can notice the recursive occurrence of “BinTree a' in the node. We
see two constructors in this datatype, Node and Leaf.
The Node constructor expects some value of type a and two subtrees
of type BinTree a, and the Leaf` constructor has no
parameters. In Haskell:

Notice that our list also has two constructors, namely the (:)
constructor that adds an element and the constructor for the empty list,
[]. Analogously we have the Node and Leaf
constructors. If we were allowed to use the (:) and []
constructor in our own Haskell code, the datatype for a list would look like
this:

1

dataLista=(:)a(Lista)|[]

Also, it is customary to keep the arguments for the functions in the same order
as the constructors are defined in the datatype, and to name the identifiers
containing the functions the same as the constructor function but in lowercase.
Applying this we get:

I left out the result type of this fold, try to find it yourself before
continuing.

By following our code we can see that every case, the case for Node
and the one for Leaf, result in a BinTree a.
Consequently the complete result of the function is a BinTree a

Now recall that we previously used a fold to calculate the sum of a list. With
that fold we were not restricted to a list. Which is also clearly visible by
looking at the type of foldr it contains only type variables. As we
want to calculate sum of the elements in this tree, which is something of type
a and not of type BinTree a we have to revise the type
of our fold. Notice the recurrence of the datatype in it’s declaration,
BinTree a. We will replace all of these occurrences in the types of
our functions with a free type variable, say r:

Keep in mind that I used ‘eta reduction’ in the above code. This means that the
last parameter (in this case the tree) isn’t explicitly specified as it would
appear at the very end of the parameter list and ath the very end of the
definition. (More on
eta reduction.) So, now let’s do something with this fold. Suppose we have
the following tree:

The type of our foldBinTree is now more compact. However, there will be
datatypes that contain a larger sum of constructors that also may have more or
less parameters than in our case. Defining the type of the fold on those
datatypes as we have done before will inevitably lead to very clumsy type
signatures. The idea is that we split up the section that denotes our functions
into a separate type, namely the algebra.

So now we define an algebra for our data structure. To do this we again look at
each data constructor and determine it’s type. The fold function takes care of
the recursion, so applying this thought consequently gives us the following
types and fold.

Keep in mind that we have to change the type of our fold, but not the definition
of the fold itself!

That’s it for now. If you did not understand everything by the end of this
article, don’t panic. It will sink in eventually. Let this rest a day or two,
and then read this article again and you’ll understand folds better. :)

In addition to my previous post where I discussed the initial
setup of your application with CI (CodeIgniter), I’ll use this post to
provide a method of setting up your environment for multiple applications.

This post is an revised version of ‘Extending the V in MVC on the web’ of November 9, 2008.

When I first started working with the MVC method it was with my own framework.
After noticing that maintaining my own framework would be very time-comsuming I
embarked on the search for a free, fast and widely supported PHP web framework.
The one I found that time was ‘CodeIgniter’.

After working on different projects I noticed that most websites present the
same data to the visitor in several different formats. Think of RSS/Atom for
blog posts for use in an RSS reader together with the (x)html versions.

While essentially providing the same data to the visitor the programmer of the
website has to put sizable amount of work to add little extra functionality in
the form of an RSS feed. Repeating a lod of code for input validation, data
retrieval from the database and creating extra routes into the application. As
you can imagine this could grow into a tedious job.

I’ll be describing techniques known and in use today, but reinvented each time
again as a (new) developer starts working on an web application. Here we’ll be
giving them name and be describing them.

If you’re struggling with your IDE to add an COM(+) object to your project you
should look in the .drp file of your project. If you include ‘ComServ’ in the
uses list you should be fine. :) Now you’re able to add an COM(+) object to your
project using add->new.