How to Setup AFP on Debian Lenny

| Comments

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.

To this extent I searched and found a nice tutorial: Setting up Apple Filing Protocol and Bonjour under Debian.

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.

Screenshot of my Debian machine in the Finder

Moving to Doctrine 1.2.x

| Comments

Here are some updates on my previous article. Doctrine meets Codeigniter.

Do not forget to add the following autoload directive to your hooks/doctrine.php and the doctrine.php cli:

[php]spl_autoload_register(array(‘Doctrine’, ‘modelsAutoload’));[/php]

Debian Lenny and the Haskell Platform

| Comments

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.

[bash] apt-get install build-essential libghc6-opengl-dev libghc6-glut-dev libeditline-dev libedit2 libedit-dev [/bash]

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:

[bash] patch -p0 haskell-platform-2009.2.0.2/scripts/install.sh Index: haskell-platform-2009.2.0.2/scripts/install.sh =================================================================== — haskell-platform-2009.2.0.2.orig/scripts/install.sh +++ haskell-platform-2009.2.0.2/scripts/install.sh @@ -34,13 +34,23 @@ install_pkg () { fi }

+# 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]

And done! :)

Datatypes and Folds: Part II

| Comments

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.

  1. Determine which datatypes are used (previously there was only one); This step is very simple if you already have the algebra.
  2. for each of these datatypes exhaustively define a fold function;
  3. 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:

  1. Determine which datatypes are used (previously there was only one); This step is very simple if you already have the algebra.
  2. for each of these datatypes exhaustively define a fold function or check whether such a fold function already exists;
  3. 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.

Doctrine: Unable to Parse String: Unable to Parse Line 0 (

| Comments

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.

Haskell Datatypes and Folds: Part I

| Comments

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:

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

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

1
2
3
4
product :: [Int] -> Int
product []     = 1
product (x:xs) = x * product xs
-- product [1..4] = 24

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.

1
2
3
4
5
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)
-- 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:

1
2
3
idList :: [a] -> [a]
idList list = foldr (:) [] list
-- Recall: [1,2,3,4,5] == 1 : 2 : 3 : 4 : 5 : []

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.

1
2
3
sumList :: [Int] -> Int
sumList list = foldr (+) 0 list
-- sumList [1..4] = 10

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.

1
2
sumList :: Num a => [a] -> a
sumList list = foldr (+) 0 list

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:

1
2
3
4
$ ghci
Prelude> let sumList = foldr (+) 0
Prelude> sumList [1..1000000]
*** Exception: stack overflow

Now try:

1
2
3
4
$ ghci
Prelude> let sumList = Data.List.foldl' (+) 0
Prelude> sumList [1..1000000]
500000500000

For a complete overview and analysis on foldr and foldl please read A tutorial on the universality and expressiveness of fold, by Graham Hutton.

Trees

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:

1
data BinTree a = Node a (BinTree a) (BinTree a) | Leaf deriving (Show, Eq)

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:

1
2
Node :: a -> BinTree a -> BinTree a -> BinTree a
Leaf :: BinTree a

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
data List a = (:) a (List a) | []

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:

1
2
3
4
foldBinTree :: (a -> BinTree a -> BinTree a -> BinTree a) -> (BinTree a) -> BinTree a -> ??
foldBinTree node leaf = f
  where f (Node x left right) = node x (f left) (f right)
        f (Leaf)              = leaf

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:

1
2
3
4
foldBinTree :: (a -> r -> r -> r) -> (r) -> BinTree a -> r
foldBinTree node leaf = f
  where f (Node x left right) = node x (f left) (f right)
        f (Leaf)              = leaf

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:

1
2
3
4
5
6
7
8
9
bintree = Node 1
            (Node 2
              (Node 3 Leaf Leaf)
              (Node 3 Leaf Leaf)
            )
            (Node 2
              (Node 3 Leaf Leaf)
              (Node 3 Leaf Leaf)
            )

A visual representation:

            1
          /  \
         2    2
        / \  / \
       3   3 3  3

Now we can define several traversals over this tree. Let’s calculate the sum of all values in the tree.

1
2
3
sumBinTree :: Num a => BinTree a -> a
sumBinTree = foldBinTree (\val res_left res_right -> val + res_left + res_right)
                         0

Algebras

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!

1
2
3
4
5
type BinTreeAlgebra a r = (a -> r -> r -> r, -- Node
                           r -- Leaf
                          )

foldBinTree :: BinTreeAlgebra a r -> BinTree a -> r

Now we can again define a sum on all Num a trees. Notice that we went from to seperate parameters for the functions to one tuple with two elements.

1
2
3
sumBinTree :: Num a => BinTree a -> a
sumBinTree = foldBinTree (\val res_left res_right -> val + res_left + res_right,
                          0)
1
2
3
4
5
$ ghci bintree.hs
*Main> bintree
Node 1 (Node 2 (Node 3 Leaf Leaf) (Node 3 Leaf Leaf)) (Node 2 (Node 3 Leaf Leaf) (Node 3 Leaf Leaf))
*Main> sumBinTree bintree
19

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. :)

Extending the v in MVC - Revisited

| Comments

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.

Adding COM(+) to Your Delphi Project

| Comments

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.

Setting Up CodeIgniter - Basics

| Comments

In this post I’ll show how to set up CodeIgniter in a way that your code and configuration (passwords!) are safe. It will involve moving the “system” and “application” outside the (public) document root.

Seperating both <em>system</em>' and application’ has obvious advantages for maintainance and for reusibility. Using a seperate `www’ directory enables you to publish all your application specific JS/CSS and other public files.