# Four nines

A really interesting problem is the four nine problem. The problem is this:
You have to generate as much integers as possible. You have at your disposal 4 nines (9) and 5 operators (+,-,*,/,%). You may combine these as you please and you can use parenthesis at your hearts content. But you can only use four nines. You have to find all the integers and give the expression to generate them.
The most straightforward solution is to make a small language with four operators, create an abstract syntax tree and then generate all the solutions by rotating, shifting etc the tree. This works fine. It is a brute force method, but if you do it right, you won't generate invalid solutions. It works and it is extensible. But generation is difficult. Although testing is simple.
Normally one would search for a smarter method, but today I choose for a dumber, but interesting method to search a space for solutions, which is bigger than the solution space of the four nine problem. This space is the space of unsigned integers up to a size of 17 bits.

## Encoding

How can we translate the original problem to a pile of natural numbers? Actually it is very easy. We encode every expression as follows:
A expression of the form (with arbitrary parenthesis) 9 o 9 o 9 o 9 can be represented by a bitstring.
First we enumerate the operators:
```+ -> 000
- -> 001
* -> 010
/ -> 011
% -> 100
```

We can easily see, why this space is bigger than the actually space with solutions. Not all operators are valid. 111 for example is not an operator.
We can encode the numbers and the parenthesis together:
```9 -> 00
9) -> 01
(9 -> 10
(9) -> 11
```

Together we can write an expression as a bitstring:
```9  |  +  | (9 | / | 9) | %  | 9
00 | 000 | 10 |011| 01 |100 | 00
```

## Testing solutions

Generation is now easy. We just need to add one to the previous found potential solution. The first potential solution is 0, the second potential solution is 1. One bitstring has the size of 17 bits. We are essentially going to code this pipeline: generate new potential solution >>= test potential solution >>= print out solution. I have chosen perl6 for the task, because hyperoperators (see: http://perl6advent.wordpress.com/2009/12/06/day-6-going-into-hyperspace/ for a good explanation) are very handy when working with bit slicing code and because they have a coding contest running with this problem in it and to show the elegance of perl6. To help the code a bit, we create a special type to ensure we are not going below zero and we write the generation function.
```subset Int::Positive of Int where { \$_ >= 0 };

sub nextBitString (Int::Positive \$x) {
return \$x + 1;
}
```
This is essentially enough to start attacking the problem. Only have to print out and done. But not all solutions are valid solutions. So we need a function to weed them out. For example the bitstring:
```)9  +  (9  /  9)  +   9
10 000 10 011 01 000 00
```
Is not a valid expression. So we need a mechanism to check these strings.

## Things we can check

The operators are always on a fixed position. They are one position 2, 7, 12. They are always 3 bits long and we know the invalid operators (101, 110, 111). We can check this in three lines of code with the help of hyperoperators:
```    # for some solution \$x
my Int @inv = (5,6,7);
my Int @pos = (\$x <<+><< (2,7,12)) >>+&>> 7;

if @pos >>===>> any(@inv) {
return False;
}
```
This looks very dense. So what happens here? First I make an array with the three invalid operators (line 1). The second line is the hard one. First I do a numeric shift to the right, while I distribute scalar on the left over the array on the right yielding a array again. (\$x <<+><< (2,7,12) Then I am selecting only the first three bits, for 111 is 7, by distributing the scalar on the right over the array on the left, which yields an array again. Maybe spreading out is a better word. Now I have selected all the operators of the expression in one line of code. That is pretty cool. Then I do the same trick, I can use the hyperoperator version of the identity operator to check if any of the operators (@pos) are one of the invalid ones. If they are, I reject this solution.

## Are we balanced?

The next thing we have to check is the parenthesis. For this we need a simple finite state machine with states: n = 0..Inf and the following transition function:
```( n -> n + 1
) n -> n - 1
* n -> n
```
The state machine has the following output functon:
```f 0 = True
f _ = False
```
And begin state n = 0. With this machinery, we can check if the parenthesis are balanced or not. Again in perl6 we can use for elegance hyperoperators to retrieve all the parenthesis: The parenthesis are on a fixed position (0,5,10,15) and have a fixed size (2 bits), thus reusing the same trick we yield the code:
```@pos = (\$x <<+><< (15,10,5,0)) >>+&>> 3;
```
The state machine is easily coded and we can even add a small short cut, to make it faster, because n < 0 is a invalid state and the state machine should immediately reject all the input.
```    for @pos -> \$pos {
given \$pos {
when 1 {
\$n -= 1;
}
when 2 {
\$n +=1;
}
}
if \$n < 0 {
return False;
}
}
if \$n == 0 {
return True;
} else {
return False;
}
```
Remember that '(' was encoded as 10 == 2 and ')' is encoded as 01 == 1.

## Evaluating the bitstrings

The evaluator have to do two things. Evaluate the expression. And give a human readable version back. The easiest way is to generate a valid perl6 expression. Run it through eval and give back the string. The strategy to do this is simple. We select every parenthesis and every operator. Zip them together and output them as string. First an parenthesis then an operator.
```    my Int @nrs = (\$x <<+><< (15,10,5,0)) >>+&>> 3;
my Int @ops = (\$x <<+><< (12,7,2)) >>+&>> 7;
my Str \$out = "";

for @nrs Z (@ops) -> Int \$nrs , Int \$op {
given \$nrs {
when 0 {
\$out ~= "9";
}
when 2 {
\$out ~= "(9";
}
when 1 {
\$out ~= "9)";
}
when 3 {
\$out ~= "(9)";
}
}
given \$op {
when 0 {
\$out ~= " + ";
}
when 1 {
\$out ~= " - ";
}
when 2 {
\$out ~= " * ";
}
when 3 {
\$out ~= " / ";
}
when 4 {
\$out ~= " % ";
}
}
}
return (\$out, eval(\$out));

```
Testing and oops, it didn't work. It will only output expressions of the form 9 o 9 o 9. And more horror comes. Some of them are not valid. Why does this happen? The answer is simple. If you zip two arrays the following law always holds:
```length (Z xs ys) == min(length xs, length ys)
```
So I need to lengthen the @ops array with one member. And it has to be a member, which doesn't evaluate to a string. SO the correct code must be:
```    my Int @ops = (\$x <<+><< (12,7,2)) >>+&>> 7, -1;
```
This solves the problem, because the length of the zipped array is now 4. The last operator gets never printed and we get valid expressions of the form: 9 o 9 o 9 o 9.

## Patching it all together

The last thing we have to do is to generate all possible solutions. And then test them and print the valid ones out.
```for 0..(2**17 - 1) -> \$i {
my Int \$string = \$i;
my Bool \$valid = validBitString(\$string);
if \$valid {
my (\$res, \$un) = evaluator(\$string);
"\$res -> \$un".say;
}
if \$i % 1000 == 0 {
"Done: \$i".say;
}
}
```
I hope you enjoyed this post. The whole script is on: http://hpaste.org/65101

## donderdag 8 maart 2012

### Using FFI to use a LibExiv2 in haskell

Haskell has a very well developed Foreign Function Interface. But one of the problems with the FFI is that it is specialized for C.

For a project in our company we needed an alternative to libexif, because the library has problems with reading binary blobs embedded in the exif data.

LibExiv2 is a perfect candidate to use, but gave rise to some technical challenges to overcome. The biggest challenge was, how to deal with auto_ptr's. We couldn't use the auto_ptr to create a StablePtr, which we can use with FFI in haskell.

First some basics of LibExiv2:

Exiv2 can open any image format. They provide a general function for opening files. This is Exiv2::ImageFactory::open. After that we can read the metadata with an object method. readMetaData. This reads the exif data from the image file. After we have done this, we can get an Iterator (some sort of Foldable-like structure) to search for certain keys and their values.

Exiv2::ImageFactor::open gives back an auto_ptr. An auto_ptr is a template class, which behaves like a pointer. But differs when a pointer leaves it scope, then it will be destroyed automagically and more important it is not a real pointer. It only behaves as a pointer, it memory address is stored in the template class.

So when we tried to pass the auto_ptr as StablePtr to the haskell side, we got an segmentation fault. After some research we concluded the following happened:

We retrieved the pointer from the auto_ptr. Then we passed this to the haskell side. But then the auto_ptr vanished from the scope, destroying the pointer in the process. Haskell then passed the original pointer back, but at that time it didn't exist anymore.

The solution was really simple. We created a wrapper around the auto_ptr:

``` struct Context { Exiv2::Image::AutoPtr autoptr; }; ```

By carefully code, we let the auto_ptr never escape an existing scope. And converting only the pointer of the context to a haskell stableptr. This way we could safely send it to the haskell side.

As an example of how to use this trick, I will take some excerpts from the library:

``` /* This function opens a new image and creates and Exiv2::Image::AutoPtr then wrap it in a Context to protect it from vanishing */ HsPtr openContext(const char * f){ std::string file(f); Exiv2::Image::AutoPtr image = Exiv2::ImageFactory::open(file); Context * c = new Context; assert(image.get() != 0); // assign the auto_ptr to the new context c->autoptr = image; c->autoptr->readMetadata(); // Cast it to a haskell pointer return (HsPtr)c; } /* Later in the code we can restore the haskell pointer back to a context */ Context * ImagefromStablePtr(HsPtr p){ return ((Context *)p); } /* And then use it to get all the keys from the exif data (from haskell to haskell) */ HsPtr getExifKeysIterator(HsPtr p){ assert(p != 0); Context * ctx = ImagefromStablePtr(p); // As long as the autoptr is not leaving his context it will exists. Exiv2::ExifData data = ctx->autoptr->exifData(); ExifIterator * it = new ExifIterator(); size_t size = data.count(); it->data = (char **)calloc(sizeof(char *), size); it->size = size; it->it = 0; size_t counter = 0; for(Exiv2::ExifData::const_iterator i = data.begin(); i != data.end(); i++){ std::string key = i->key(); it->data[counter] = new char[key.size()+1]; strcpy(it->data[counter], key.c_str()); counter++; } return (HsPtr)it; } ```

The rest of the job was straightforward, except for the problem to let cabal handle the build process, but I am working on that. Advice would be appreciated.

You can view the code at bitbucket: https://bitbucket.org/eklerks/libexiv2bindings/src

I haven't include the build code. But manual building is not difficult. I will update the repos if I figured out, how to let it work with cabal.

## zaterdag 8 mei 2010

### Making M4 into a functional language

One of the less used, but widely distributed macro processors (M4) can be transformed into a functional language. After reading http://www.cs.stir.ac.uk/~kjt/research/pdf/expl-m4.pdf

I decided to create some list processing functions (Foldr,Foldl,Head,Tail,Append,Prepend,Null,Sum,Filter)

To implement Foldr and Foldl I have used CPS (continuation passing style), so these functions are difficult to read, but easily testable. Just fireup haskell and try: foldr (-) 0 [3,2,1] -> 2 and foldl should give -6. So Foldl(`Sub',0,[3;2;1]) should give -6 too.

Some logic operators (Not,And,Or,isBool)

Adding support for 'lambdas' -not really, but it is close- and add support for currying.

Maybe I change it in a real project some day. It is rather fun and with foldl and foldr a lot of functions from Data.List can be ported. The real challenge is adding monads. I am not sure if that is possible yet, but I have the feeling it probably can.

Of course there is no type system, but it suprised me how easily most functions could be implemented.

An example:

Lambda(x,`eval(\$1-(\$2))')dnl
`foldr'(`x',0,[3;2;1]) is : Foldr(`x',0,t)
`foldl'(`x',0,[3;2;1]) is : Foldl(`x',0,t)

The output of this is:

foldr(x,0,[3;2;1]) is : 2
foldl(x,0,[3;2;1]) is : -6

Even cooler is that you can write your testcases in haskell. Like:

test1 = `foldr' (-) 0 [3,2,1] == Foldr(`x',0,`[3;2;1;]')

Which gives us in ghci:

test1 = foldr (-) 0 [3,2,1] == (2)
ann@ann-desktop:~\$ ghci
GHCi, version 6.12.2: http://www.haskell.org/ghc/ :? for help
Prelude> foldr (-) 0 [3,2,1] == (2)
True
Prelude>

This is the minilib, it is somewhat dense, but so I could use it in a project:
changecom(`#',`')dnl
dnl# `Id`
define(Id, \$1)dnl
dnl# `Lambda'
define(Lambda, `define(\$1, `\$2')')dnl
define(Curry1, `define(\$1,`\$2'(\$3,\$`'1,\$`'2,\$`'3,\$`'4))')dnl
define(Curry2, `define(\$1,`\$2'(\$3,\$4,\$`'1,\$`'2,\$`'3,\$`'4))')dnl
define(Curry3, `define(\$1,`\$2'(\$3,\$4,\$5,\$`'1,\$`'2,\$`'3,\$`'4))')dnl
define(Curry4, `define(\$1,`\$2'(\$3,\$4,\$5,\$6,\$`'1,\$`'2,\$`'3,\$`'4))')dnl
define(Curry5, `define(\$1,`\$2'(\$3,\$4,\$5,\$6,\$7,\$`'1,\$`'2,\$`'3,\$`'4))')dnl
define(Curry6, `define(\$1,`\$2'(\$3,\$4,\$5,\$6,\$7,\$8,\$`'1,\$`'2,\$`'3,\$`'4))')dnl
dnl# `Logical operators'
define(True, 1)dnl
define(False,0)dnl
define(Not, `ifelse(\$1, True, False, `ifelse(\$1, False, True, `errprint(Not a bool)')')')dnl
define(isBool, `ifelse(\$1, True, True, `ifelse(\$1, False, True, False)')')dnl
define(And, `ifelse(\$1, True, `ifelse(\$2, True, True, False)', False)')dnl
define(Or, `ifelse(\$1, True, True, `ifelse(\$2, True, True, False)')')dnl
dnl# `List operators'
define(Empty, [])dnl
define(Prep, `ifelse(\$2,[],[\$1;],[\$1;`substr(\$2,1,decr(len(\$2)))')')dnl
define(App, `ifelse(\$2,[],[\$1;],`substr(\$2, 0, decr(len(\$2)))'\$1;])')dnl
define(Next, `substr(\$2,\$1,1)')dnl
define(Getpos, `ifelse(Next(\$1,\$2),\$3,\$1,`Getpos(incr(\$1), \$2, \$3)')')dnl
define(Tail, `ifelse(\$1,[],`errprint(tail: empty list)',[`substr(\$1,incr(Getpos(0,\$1,;)))')')dnl
define(Null, `ifelse(\$1,[],True,False)')dnl
dnl# `Foldr continuation passing style'
define(Foldr, `ifelse(Null(\$3),True,\$2,`_Step(`\$1',\$2,\$3,`Foldr')')')dnl
dnl# `Foldl continuation passing style'
define(Foldl, `ifelse(Null(\$3),True,\$2,`_Stepl(`\$1',\$2,\$3,`Foldl')')')dnl
dnl# `Sum example usage of Foldr'
define(Plus, `eval(\$1+\$2)')dnl
define(Sum, `Foldr(`Plus',0,\$1)')dnl
dnl# `Filter'
dnl# `Filter creates an locally scoped curried function, implemented withdefine..undefine'
dnl# ` ```\$1''' is just a trick to get the function unpacked at the right place. Every passing
dnl# `removes a `' from the functionname'
define(_Stepf, `ifelse(\$1(\$2), True, Prep(\$2, \$3), \$3)')dnl
define(Filter,`Curry1(__Stepf,`_Stepf',```\$1''')Foldr(`__Stepf',Empty,`\$2')undefine(`__Stepf')')dnl
dnl# `Example foldr and foldl'
define(t, Prep(3,Prep(2,Prep(1, Empty))))dnl
Lambda(x,`eval(\$1-(\$2))')dnl
`foldr'(`x',0,[3;2;1]) is : Foldr(`x',0,t)
`foldl'(`x',0,[3;2;1]) is : Foldl(`x',0,t)

## donderdag 18 februari 2010

### Some stuff I miss in javascript

I haven't go a lot of time, so this will be a short one.

There is a lot of stuff I miss in javascript. I made an small lib for myself, which I want to share.

First I added some OO patterns:

Decorator,
Proxy,
Observer,
Observable,
Strategy,
Chain,
Chainable exceptionhandlers

I added a logger, which plays nicely with firebug. And some functional stuff like:

foldr,
foldl

A function, which returns a function, which allow partial function application:

pfunc

And a function, which gives any object an fluent interface (useful for loggers):

fluentize

And also added the function merge to the Array object. Here is the small lib:

There are probably some bugs and I haven't documentation, but on request I can add some examples.

```/* Some functions I miss in javascript */

/* Haskell style partial function application */

/*
Transforms a function of type:
( (a, b) -> c)
to
a -> b -> c
so if we have a function
f(x,y,z) -> x - y + z
we can do this now:
f(1,y,z) = g(y,z) = 1 - y + z
or this:
f(1,2,z) = g(z) = 1 - 2 + z
or this
f(x,y,z) = f(x,y,z);

use this class as
function min(a,b,c){
return a - b + c;
}
var pmin = pfunc(min);
var t = pmin(1)(2)(3);
print(t);

*/

function pfunc(func, i, acc){
if(!i){ i = 0; acc = new Array(); }
if(i == func.arity) return func.apply(func, acc);

return function(){
acc.merge(arguments);
return pfunc(func, i + arguments.length, acc);
}
}
/* Makes an object fluent */

function fluentize(obj){
var newobj = {};
for(key in obj){
var val = obj[key];
var valn;
if(typeof(val) == 'function'){
newobj[key] = function(){
val.apply(obj, this.arguments);
return obj;
}

} else {

newobj[key] = val;
}
}
return newobj;
}
/* Foldr and fold */

function foldr(list, func, acc){
var list = list.reverse();
if(list.length == 0) return acc;
for(var i = 0; i < list.length; i++){
var val = list[i];
if(typeof(val) != 'string' && typeof(val) != 'boolean' && typeof(val) != 'number') continue;
acc = func(val,acc);
}
return acc;
}
function foldl(list, func, acc){
if(list.length == 0) return acc;
for(var i = 0; i < list.length; i++){
var val = list[i];
if(typeof(val) != 'string' && typeof(val) != 'boolean' && typeof(val) != 'number') continue;
acc = func(acc, val);
}
return acc;
}

/* Very important, array merge: */

Array.prototype.merge = function(arr){
for(var i = 0; i < arr.length; i++){
this.push(arr[i]);
}
}
/*  Voor ieder een hel
Voor de enkeling een hemel
maak je keuze snel

*/
/*
Function which can ensure an element exists.
callback should be return true or false
*/

function ensure(callback, cps){
function _ensurethis(){
if(callback()){
cps();
return;
}
ensure(callback, cps);
}
window.setTimeout(_ensurethis, 10);
}

/* Some OO patterns, which are very useful: */

/* Extends an object with other objects
* @function extendedObject = Extend(obj, obj1, obj2, obj3 .. objn)
*/

function Extend(){
var obj = arguments[0];
for(var i = 1; i < arguments.length; i++){
for(key in arguments[i]){
obj[key] = arguments[i][key];
}
}
return obj;
}
/* Couple of methods, which let us forward calls to an inner object,
very useful to build decorators, proxies etcetera */
function ForwardCall(){
}

/* Forward calls to an inner object */

ForwardCall.prototype.forwardCall = function(func) {
this[func] = function(){
return this.innerCall(func, arguments);
}
}
ForwardCall.prototype.innerCall = function (func, args){
return this.obj[func].apply(this.obj, args);
}

/* Decorator object */

Decorator.prototype = ForwardCall.prototype;

function Decorator(obj){
this.obj = obj;
for(key in this.obj){
var val = this.obj[key];
if(typeof(val) == 'function'){
this.forwardCall(key);

}
}
}

/* Proxy object */

Proxy.prototype = ForwardCall.prototype;

function Proxy(obj){
this.obj = obj;
for(key in obj){
var val = this.obj[key];
if(typeof(val) == 'function'){
this[key] = function(){
var args = this.before(key, arguments);
ret = this.innerCall(key, args);
return this.after(key, ret);
}
}
}
this.before = function(func, args){
return args;
};
this.after = function (func, ret){
return ret;
}
}

/* Observable */

function Observable(){
}
if(typeof(this.observers) == 'undefined'){
this.observers = new Array();
}
this.observers.push(observer);
}
Observable.prototype.updateObservers = function (message){
for(observerid in this.observers){
var observer = this.observers[observerid];
}
}

/* Observer */

function Observer(){

}

}

/* Implementation of the strategy pattern */

function Strategy(){
this.strategies = new Array();
this.createStrategy = function (func, test){
return {func: func, test: test};
};
this.strategies.push(this.createStrategy(func, test));
return this.strategies.length;
};
this.setDefaultStrategy = function (func){
this.defaultStrategy = func;
};
this.removeStrategy = function (id){
this.strategies[id] = null;
};
this.run = function() {
var args = arguments;
for(key in this.strategies){
if(this.strategies[key] != null){
var strategy = this.strategies[key];
if(strategy['test'].apply(this, args)){
return strategy['func'].apply(this, args);
}
}
}
return this.defaultStrategy.apply(this, args);
}

}

function Chain(){
}
function Chain(test, func){
this.func = func;
this.test = test;
this.next = null;
this.run = function(){
if( this.test.apply(this, arguments) ){
return this.func.apply(this, arguments);
}
if(this.next != null){
return this.next.run.apply(this.next, arguments);
}
return null;
}
if(this.next == null){
this.next = new Chain(test,func);
return;
}
}
}

ExceptionHandler.prototype = ForwardCall.prototype;
function ExceptionHandler (obj){
this.obj = obj;
this.strategy = new Strategy;
this.strategy.setDefaultStrategy(function(ex,key){
print ("Uncaught Exception calling: " + key);
print(ex);
return;
});

this[key] = function(){
try {
this.innerCall(key, arguments);
} catch (e){
this.strategy.run(e, key);
}
}
}

for(key in this.obj){
var val = this.obj[key];
if(typeof(val) == 'function'){
return this.next.run.apply(this.next, arguments);
}
return null;
}
if(this.next == null){
this.next = new Chain(test,func);
return;
}
}
}

ExceptionHandler.prototype = ForwardCall.prototype;
function ExceptionHandler (obj){
this.obj = obj;
this.strategy = new Strategy;
this.strategy.setDefaultStrategy(function(ex,key){
print ("Uncaught Exception calling: " + key);
print(ex);
return;
});

this[key] = function(){
try {
this.innerCall(key, arguments);
} catch (e){
this.strategy.run(e, key);
}
}
}

for(key in this.obj){
var val = this.obj[key];
if(typeof(val) == 'function'){
}
}
}
}

/* Inspection function */
function Inspect(obj, depth, i, indent){
if(!depth){
depth = 5;
}
if(!i){
i = 0;
indent = '';
}
for(key in obj){
var type = typeof(obj[key]);
print (indent + type  + ": " + key);
if((type == 'object' || type == 'function' ) && i < depth){
Inspect(obj[key], depth, i + 1, indent + "  ");
}
}

}
/* We need to define a print function, to work with all the classes above:
*/
function print(str){
Logger.getInstance().startGroup('print').log('from: ' + arguments.callee.caller.toString()).log(str).endGroup();
}

/* HTML generating functions */

/* Simple positioning function */
function putHTML(pos){
return function(data){

Logger.getInstance().startGroup('putHTML');
Logger.getInstance().log('position data at: ' + pos);
\$(pos).html(data);
Logger.getInstance().endGroup();
}
}
/* Javascript logger, logs to firebug, this an singleton, on non development site, we have to run Logger.getInstance().setSilence(),
then it shuts up */
function Logger(){
this.silence = false;
}

Logger.getInstance = function(){
if(!Logger.instance){
Logger.instance = /*fluentize(*/new Logger();//);
}
return Logger.instance;
}
Logger.prototype.setSilence = function(silence){
if(!silence){
silence = true;
}
this.silence = silence;
}
Logger.prototype.startGroup = function(name){
if(this.silence) return;
console.group(name);
return this;
}
Logger.prototype.endGroup = function(){
if(this.silence) return;
console.groupEnd();
return this;
}
Logger.prototype.log = function (logline, errorlevel){
/* formatted mode */
if(!console || this.silence){
return;
}
if(typeof(logline) == 'object'){
this.multiline(logline, errorlevel);
}
if(errorlevel == 'error'){
console.error(logline);
} else
if(errorlevel == 'warn'){
console.warn(logline);
} else {
console.info(logline);
}
return this;
}
Logger.prototype.multiline = function(loglines, errorlevel){
console.group('Object inspector:');
console.dir(loglines);
console.groupEnd();
return this;
}

```

# An example implementation of a applicative functor in python

I haven't had a lot of time lately, so I have to break my promise made in my previous blog. No javascript decorators this time. This is because I am studying Haskell. Therefore I changed the subject and will show an example implementation of a small combinators library based on applicative functors.

First I will explain shortly how to interpret the Haskell type system. Then I will talk about functors and applicative functors. Then I will show you how to implement these in python.

Haskell is a static strong typed language, unlike python, which is dynamic strong typed. Therefore every function in haskell must have a known type signature at compile time. These can be specified by the programmer in the source or can be omitted so the compiler has to sort it out itself. These signatures look like this:
```func :: (Num a) => a -> a -> a
```
func is a function, which takes in 2 numeric arguments and returns one numeric argument. All functions in Haskell are first class, so this is also possible:
```func :: (a -> b) -> a -> b
```
This is a function which takes in a function and a variable of type a and returns a variable of type b.

The signatures are right associative, so this:
```func :: (a -> b) -> a -> b
```
is the same as this:
```func :: (a -> b) -> (a -> b)
```
This mean, that if I call func with one argument it returns a function. Thus all functions are curried!

This is a rather short explaination, but enough to understand the rest of the story. Lets go on to the functors.

## What are functors

Functors in most languages are callable objects. In Haskell they are special mathematical objects. I won't and can't dive to deep into this matter, because I never had category theory, but I can try to explain what it is. A functor in Haskell is a data structure (again this is rather simplified), which has a special function attach to it with the following type signature:
```fmap :: (Functor f) => (a -> b) -> f a -> f b
```
It takes in a function which maps a to b and functor of type a and it returns a functor of type b. In most programming languages there are functors. In Haskell they are named explicitly. E.g. Lists in python are a functor, fmap here is map:
```map(function, iterable, ...)¶
```
So map takes in a function and a iteratable (like a list) and applies the function to each member of the list and then returns the modified list. Almost everything can be a functor, we only have to define its own fmap:
```class BoringFunctor:
def __init__(self, res):
self.res = res
@staticmethod
def fmap(func, bf):
return BoringFunctor(func(bf.res))

t = BoringFunctor(5)
p = BoringFunctor.fmap((lambda x: x + 5), t)
#prints 10
print p.res
```
Well that was easy, lets go on to applicative functors.

## Applicative functors

Applicative functors have a couple of extra functions. These are:
```pure :: a -> f a
```
and
```<*> :: f (a -> b) -> f a -> f b
```
Pure simply returns a new applicative functor. <*> is somewhat more puzzling. This takes in a functor, which carries a function of type a -> b and a functor, which carries an variable a. It returns a functor of variable b. What can we do with this? First I have to add <*> is an left associative infix operator.

We can define fmap:
```fmap f x= pure f <*> x
```
We can define an fmap function, which takes 2 arguments -`fmap` makes fmap infix-
```fmap2 :: (a -> b -> c -> d) -> f a -> f b -> f c -> f d
fmap2 f a b = f `fmap` a <*> b <*> c
```
This is looks rather difficult. Let take the left associativeness into account:
```fmap3 f a b c = (((f `fmap` a) <*> b) <*> c)
```
We could break this into steps:
```--- (a -> b -> c -> d) -> f a -> f (b -> c -> d)
fmap3' f a = f `fmap` a
-- f (b -> c -> d) -> f b -> f ( c -> d)
fmap3'' f b = f <*> b
-- f (c -> d) -> f c -> f d
fmap3''' f c = f <*> c
fmap3 f a b c = fmap3''' (fmap3'' (fmap3' f a) b) c
```
With each step the function gets more and more curried.

## Putting it into practice

We are going to setup a combinator library for communicating with the database. Let first define our functor:
```class AppFunctor:
"""Applicative functor (well it has grown to a monad)"""
_inner = None
def __init__(self,inner):
self._inner = inner
# (a -> b) -> f a -> f b
@staticmethod
def fmap(func, functor):
inner = functor.getInner()
inner = func(inner)
return AppFunctor.pure(inner)
# a -> f a
@staticmethod
def pure(inner):
return AppFunctor(inner)
```
It is just a class with two static methods. fmap an pure. I have added the type signature so I don't get confused.
pure returns just a new AppFunctor. And fmap unpacks the functor apply the function and returns the return value in a new AppFunctor. That was rather easy. Now we are creating <*>. Unfortunately it isn't possible to create your own operators in python, so I chose -, which works.
```# f (a -> b) -> f a -> f b
@staticmethod
def ap(apfunctor, connfunctor):
inner = connfunctor.getInner()
func = apfunctor.getInner()
return AppFunctor.pure(func(inner))
def __sub__(self, other):
return AppFunctor.ap(other, self)

```
As we can see, f <> b unpacks f and b, and then applies b to f after this it returns the return value in a new AppFunctor. Here I create a couple of methods, which aren't related to applicative functors, but can be handy:
```# extract (comonad) f a -> (f a ->   f b) -> f b
return func(self)
# normal bind  f a -> (a -> f b) -> f b (Not used in this tutorial,
#but can be very powerfull)
def __ge__(self, func):
inner = self.getInner()
return func(inner)
# f (a -> b -> c) -> a -> f ( b -> c )
# injects an argument into functor
def inject(self, arg):
func = self.getInner()
return func(arg)
def __mul__(self, arg):
return self.inject(arg)
```
Now we need a simple decorator, which can turn functions into applicative functors:
```def app(func):
def new(*args):
return func(*args)
return AppFunctor.pure(new)

```
We can use this as follow:
```@app
def printResult(obj):
...
```

## The whole class

```def app(func):
def new(*args):
return func(*args)
return AppFunctor.pure(new)

class AppFunctor:
"""Applicative functor (well it has grown to a monad)"""
_inner = None
def __init__(self,inner):
self._inner = inner
# (a -> b) -> f a -> f b
@staticmethod
def fmap(func, functor):
inner = functor.getInner()
inner = func(inner)
return AppFunctor.pure(inner)
# pseudo bind f a -> (f a ->   b) -> f b
return func(self)
# normal bind  f a -> (a -> f b) -> f b
def __ge__(self, func):
inner = self.getInner()
return func(inner)
# a -> f a
@staticmethod
def pure(inner):
return AppFunctor(inner)
# f (a -> b) -> f a -> f b
@staticmethod
def ap(apfunctor, connfunctor):
inner = connfunctor.getInner()
func = apfunctor.getInner()
return AppFunctor.pure(func(inner))
def __sub__(self, other):
return AppFunctor.ap(other, self)
def getInner(self):
return self._inner
# f (a -> b) -> a -> f b
# injects an argument into functor
def inject(self, arg):
func = self.getInner()
return func(arg)
def __mul__(self, arg):
return self.inject(arg)

```

## Lets use it

We want to make a connection to the database, run a query and retrieve the results. We want to do this with our new toy. I use MySQLdb for the communication with the database. First I need an object to hold the current cursor in and the connection:
```class ConnectionObject:
_cursor = None
_conn = None
def __init__(self, conn):
self._conn = conn
def getConn(self):
return self._conn
def getCursor(self):
return self._cursor
def setCursor(self, cursor):
self._cursor = cursor

```
And a function to connect to the database. This returns a functor:
```def connectToDb():
obj = ConnectionObject(conn)
return AppFunctor.pure(obj)
```
I need a function to fetch a cursor. This should be a applicative functor, so we can apply @app to it
```@app
def getCursor(obj):
obj.setCursor(obj.getConn().cursor())
return obj
```
And I need a function, which executes a query:
```@app
def execute(sql):
@app
def inner2(obj):
obj.getCursor().execute(sql)
return obj

return inner2
```
The inner lambda is needed to wrap the sql statement in a closure until a cursor object is passed.

And a function which fetches the results and returns the cursor object:
```def fetchAll(cfunc):
@app
def inner(obj):
return obj.getCursor().fetchall()
return cfunc - inner + lambda x: dict(obj=cfunc, results=x)
```
This function has some special things. It is used at the end of our assembly line. Now lets use our new functions.

First we make the connection and request a cursor:
```obj = connectToDb() - getCursor
```
The wrapped connection object is passed to getCursor with (-). obj is also an appfunctor

We also want to make a query:
```obj = connectToDb() - getCursor - execute * "select * from orders limit 10"
```
connectToDb is feeded to getCursor, then execute * "select * from orders limit 10" is evaluated, this yields another appfunctor. Then the result of connectToDb - getCursor is put into the result of execute * ...,

The last step is to fetch the results. Fetchall is different, because it doesn't want the result to be unpacked. This is because it is an holder of an applicative functor. Namely inner, so we have to use the (+) operator:
```test =  connectToDb() - getCursor - execute * 'select * from orders limit 10'  + fetchAll
```
Now we can see the result by unpacking test:
```pp.pprint(test['results'].getInner())
```
As you can see, we have designed a really elegant way to pull stuff from the database. You can use this on many places. It is clear what is happening. It connects to the database, gets a cursor, executes a query and then fetch it all in one rule.

## The whole file

```import sys
from MySQLdb import *
import pprint

class ConnectionObject:
_cursor = None
_conn = None
def __init__(self, conn):
self._conn = conn
def getConn(self):
return self._conn
def getCursor(self):
return self._cursor
def setCursor(self, cursor):
self._cursor = cursor

def app(func):
def new(*args):
return func(*args)
return AppFunctor.pure(new)

class AppFunctor:
"""Applicative functor (well it has grown to a monad)"""
_inner = None
def __init__(self,inner):
self._inner = inner
# (a -> b) -> f a -> f b
@staticmethod
def fmap(func, functor):
inner = functor.getInner()
inner = func(inner)
return AppFunctor.pure(inner)
# pseudo bind f a -> (f a ->  f b) -> f b
return func(self)
# normal bind  f a -> (a -> f b) -> f b
def __ge__(self, func):
inner = self.getInner()
return func(inner)
# a -> f a
@staticmethod
def pure(inner):
return AppFunctor(inner)
# f (a -> b) -> f a -> f b
@staticmethod
def ap(apfunctor, connfunctor):
inner = connfunctor.getInner()
func = apfunctor.getInner()
return AppFunctor.pure(func(inner))
def __sub__(self, other):
return AppFunctor.ap(other, self)
def getInner(self):
return self._inner
# f (a -> b) -> a -> f b
# injects an argument into functor
def inject(self, arg):
func = self.getInner()
return func(arg)
def __mul__(self, arg):
return self.inject(arg)

@app
def getCursor(obj):
obj.setCursor(obj.getConn().cursor())
return obj

@app
def execute(sql):
@app
def inner2(obj):
obj.getCursor().execute(sql)
return obj

return inner2

def fetchAll(cfunc):
@app
def inner(obj):
return obj.getCursor().fetchall()
return cfunc - inner + lambda x: dict(obj=cfunc, results=x)

def connectToDb():
conn = connect(host="assasa", passwd="sasasa", user="assasa", db="asas");
obj = ConnectionObject(conn)
return AppFunctor.pure(obj)

test =  connectToDb() - getCursor - execute * 'select * from orders limit 10'  + fetchAll

pp = pprint.PrettyPrinter(indent=4)
pp.pprint(test['results'].getInner())
```

# Update

The fetchAll function is somewhat unclean. It should return an AppFunctor. To facilitate this, I change the connectionobject as follow:
```class ConnectionObject:
_cursor = None
_conn = None
_res = None
def __init__(self, conn):
self._conn = conn
def getConn(self):
return self._conn
def getCursor(self):
return self._cursor
def setCursor(self, cursor):
self._cursor = cursor
def setResults(self, res):
self._res = res
def getResults(self):
return self._res
```
The fetch all function looks a lot nicer now and it returns an functor:
```def fetchAll(cfunc):
@app
def inner(obj):
obj.setResults(obj.getCursor().fetchall())
return obj
return cfunc - inner

```
To see the results we can do:
```test =  connectToDb() - getCursor - execute * 'select * from orders limit 10'  + fetchAll

pp = pprint.PrettyPrinter(indent=4)
pp.pprint(test.getInner().getResults())
```
We even could simplify the changeAll function:
```@app
def fetchAll(obj):
obj.setResults(obj.getCursor().fetchall())
return obj
```
The statement now becomes:
```test =  connectToDb() - getCursor - execute * 'select * from orders limit 10'  - fetchAll
```
Which is much neater than my first try.

## Full file

```import sys
from MySQLdb import *
import pprint

class ConnectionObject:
_cursor = None
_conn = None
_res = None
def __init__(self, conn):
self._conn = conn
def getConn(self):
return self._conn
def getCursor(self):
return self._cursor
def setCursor(self, cursor):
self._cursor = cursor
def setResults(self, res):
self._res = res
def getResults(self):
return self._res

def app(func):
def new(*args):
return func(*args)
return AppFunctor.pure(new)

class AppFunctor:
"""Applicative functor (well it has grown to a monad)"""
_inner = None
def __init__(self,inner):
self._inner = inner
# (a -> b) -> f a -> f b
@staticmethod
def fmap(func, functor):
inner = functor.getInner()
inner = func(inner)
return AppFunctor.pure(inner)
# comonad extract f a -> (f a ->   b) -> f b
return func(self)
# normal bind  f a -> (a -> f b) -> f b
def __ge__(self, func):
inner = self.getInner()
return func(inner)
# a -> f a
@staticmethod
def pure(inner):
return AppFunctor(inner)
# f (a -> b) -> f a -> f b
@staticmethod
def ap(apfunctor, connfunctor):
inner = connfunctor.getInner()
func = apfunctor.getInner()
return AppFunctor.pure(func(inner))
def __sub__(self, other):
return AppFunctor.ap(other, self)
def getInner(self):
return self._inner
# f (a -> b) -> a -> f b
# injects an argument into functor
def inject(self, arg):
func = self.getInner()
return func(arg)
def __mul__(self, arg):
return self.inject(arg)

@app
def getCursor(obj):
obj.setCursor(obj.getConn().cursor())
return obj

@app
def execute(sql):
@app
def inner2(obj):
obj.getCursor().execute(sql)
return obj

return inner2

@app
def fetchAll(obj):
obj.setResults(obj.getCursor().fetchall())
return obj

def connectToDb():
conn = connect(host="mysql1.sdfsdf.nl", passwd="dsfsdf", user="goodforall", db="fssdf_eu",ssl="true");
obj = ConnectionObject(conn)
return AppFunctor.pure(obj)

test =  connectToDb() - getCursor - execute * 'select * from orders limit 10'  - fetchAll

pp = pprint.PrettyPrinter(indent=4)
pp.pprint(test.getInner().getResults())
```

## woensdag 9 september 2009

### Decorators in PHP

Introduction

In this blog I will try to explain what an decorator is and when to use it. After this I will show you how to make an decorator in PHP. Then how to write an general abstract decorator class and a useful concrete class based on the abstract class.

What is a decorator?

A decorator is a design pattern, which can dynamically add and remove functionality from an existing class.

When to use it?

You usually use this in two situations.

The first one is that you cannot change the behaviour of the original class. This is very uncommon in php, but sometimes licenses won't permit changing some classes, which exhibits some annoying behaviour. By writing a decorator for this specific class, we can change or even remove the behaviour.

The second case is more common. We want to change the behaviour of our class dynamically depending on the situation. For example we write an class with outputs xml data. This class can have an getOutput method. By creating a decorator for this class, we can change the output provided by the getOutput method. For example we can create an decorator, which captures the getOutput from the original object and transform it to html.

How to create our xml decorator.

First we need a class, which outputs some xml for us. We create a very simple class for this:

```class Bookoutput {
public function getOutput(){
return '<books>
<book>
<title>Booktitle</title>
<abstract>Abstract</abstract>
<author>Author</author>
</book>
</books>';
}
}
```

Bookoutput knows one method and that is getOutput, which returns some hardcoded xml. To create a decorator, we have to define a class, which accepts an Bookoutput object in its constructor and stores it, so we can call it later in our methods. The class must also have the getOutput method like the Bookoutput class to preserve its interface:

```class BookToHTMLDecorator {
protected \$xml;
public function __construct(Bookoutput \$xml){
\$this->xml = \$xml;
}
public function getOutput(){
\$output = \$this->xml->getOutput();
return \$this->transform(\$xml);

}
protected function transform(\$xml){
\$out = '<table><tr><th>Title</th><th>Author</th><th>Abstract</th></tr>';
foreach(\$xml as \$book){
\$out .=  "<tr><td>" . \$book->title ."</td><td>"  . \$book->author . "</td><td></tr>";
}
\$out .= "</table>";
return \$out;
}
}
```

We can use the class as follow:

```\$p = new BookToHTMLDecorator(new Bookoutput);
print \$p->getOutput();
/* Output:
<table><tr><th>Title</th><th>Author</th><th>Abstract</th></tr><tr><td>Booktitle</td><td>Author</td></tr></table>
*/
```

It is important to choose good names for your decorators, because once you got the concept, their number will grow fast.

How to generalise the concept?

Writing decorators in the above way is no problem, when the number of methods in a class is small. But when I want to decorate a huge class with a billion methods, I probably want to do it another way.

Fortunately we can create an abstract decorator class, which propagate method calls magically to the decorated object, if the method doesn't exist in the original class:

```abstract class GeneralDecorator {
/* decorated object */
protected \$object;
public function __construct(\$object){
if(!is_object(\$object)){
throw new Exception('Needs to be an object');
}
\$this->object = \$object;
}
public function __call(\$method, \$args){
call_user_func_array(array(\$this->object, \$method), \$args);
}
public function __set(\$key, \$val){
\$this->object->\$key = \$val;
}
public function __get(\$key){
return \$this->object->\$key;
}

}
```

We use the magic methods (__get, __call and __set) php is providing to let the GeneralDecorator class behave exactly the same as the object we put in. Now we can implement some concrete classes. In this case I will implement an decorator, which add ArrayAccess to any class:

```class ArrayAccessDecorator extends GeneralDecorator  implements ArrayAccess {
public function offsetSet(\$key, \$value){
\$this->__set(\$key, \$value);
}
public function offsetGet(\$key){
return \$this->__get(\$key);
}
public function offsetUnset(\$key){
\$this->__set(\$key, null);
}
public function offsetExists(\$offset){

\$test = \$this->object->__get(\$offset);
if(\$test !== null){
return true;
} else {
return false;
}
}

}
```

I have use a similiar class when I had a controller which passed array's to its templates. So the page title was accessible like: \$parameters['title']. After some time I changed the template parameters into objects, so I could add methods to it, if I wanted. But this created a problem. I had to change all the templates (boring), add array access to the object (unwanted, in newer templates I don't use the old syntax) or create a decorator which does this. Which was the perfect solution. I can load it on demand and I can see there is something funky going on (the code warns about the old syntax the templates use.

### Example usage of the class:

```\$template = (object)array('test' => 'bla', 'bla' => '1', 'option' => '3');
\$template = new ArrayAccessDecorator(\$template);
print \$template['bla'] . "\n";
print \$template['test'] . "\n";
print \$template['option'] . "\n";
/* 1
3
bla
*/
```

Next time I will show you a couple of handy decorators for php and how to implement the concept in javascript (also oo-oriented, but prototype based, not class-based).