Functional.js part 2

Type clases

(This article will not contain much javascript. It contains more the consepts of functional programming that will be important when discussing more advance topice later)

What are type classes? A definition of a type class is a function that takes some type variables of a type and returns a new type that depends on thoose type variables. So it is like a function that operates on types.

This means that you have a free type variable that you can define some type constraint on a “class” of functions. This free type variable is called parametrically polymorphism. If this sound familiar to some Java and C# developers, this is also called generics.

In haskell:

1
2
3
class Eq a where
(eq) :: a -> a -> Bool
(neq) :: a -> a -> Bool

In C# code:

1
2
3
4
public interface Eq<T> {
bool eq(T x, T y);
bool neq(T x, T y);
}

In javscript code:

1
2
3
4
//+ eq :: T -> T -> Boolean
//+ neq :: T -> T -> Boolean
//No type checker :(

So why do you want this? When we can write this for every class that we needs a an equals method. What does this buy us? It seems like a zero sum game.
The win is expressiveness with type safty. You can write a definition once and use that definition for every class that needs to implement it.

Duck typeing is not safe!
Beware of the duck typeing! Don't trust that duck!

A common usecase for type is collections where the type of the collection varries. But do you want to write a implementation for every type that you put in your colletion? Probably not…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public interface Collection<int> {
bool at(int index);
int mapInt(Lambda<int, int>);
string mapString(Lambda<int, string>);
//many more methods down here...
}
public interface Collection<float> {
bool at(int index);
float mapInt(Lambda<float, float>);
string mapString(Lambda<float, string>);
//many more methods down here...
}
//... reapeat for every datatype

You want some generic data strcture that operates on the elements for some type. And these elemets in our is like a wrapper around the real type. This is the reason that we don’t need to care about the real type.

1
2
3
4
5
6
7
public interface Collection<T> {
bool at(int index);
//Q is a type variable
Q map(Lambda<T, Q>);
//many more methods down here...
}

In .NET and C# type classes are realy common. Like Enumerable<T> and List<T>. The library to process collection is LINQ that have a generic functions that don’t care what is in the collections or how the collection works.

A common library in javascript to proccess generic collections is underscore (or lodash). Which abstracts away the depedency to the value inside the collection.

In a language that has a propper type system (Damas-Hindley-Milner type system, DHM for short) like in Haskell. Such type system automaticaly supports generics, it is a requirement of such a system. If the type system encounters a functions that has a free type variable that is not type dependant then the function is automatically a generic function.
An example

1
2
3
4
// The ":" appends an elements to a list
// So x is the element and xs is the rest of the list
// So we only return the first element and ignores the rest of the list.
first x : xs = x

The type system knows that I don’t do any type dependant function calls or operators on the value. So the type system keeps the type for this function free.

1
data first :: [T] -> T

But if you add a type dependant function call to it then the function is no longer generic.

1
firstAddOne x : xs = x + 1

Then the types becomes:

1
data firstAddOne :: [Num] -> Num

So the type system automatically checks so the function that you are using only take argument that it can handle. So no unexpected behaviour happens.

How many time in JavaScript have you encountered a unexpected result because of providing a wrong type to a function.
Example:

1
2
3
4
5
6
7
var firstAddOne = function (list) {
return list[0] + 1;
};
firstAddOne(['2', '3', '4', '5']); //WRONG: "21"
firstAddOne([{a: 1}, {b: 2}]); //WRONG: "[object Object]1"
firstAddOne([2, 3, 4, 5]); //CORRECT: 3

These errors could have been avoided if we had a DHM type checker for javascript. (We will try to make a DHM type checker for javascript later in this series).

If you would have a DHM type system in your language. You would not have to write a single type in your code (There are some exeptions). And it is smarter then you! How many times have your provided the wrong type to the compiler when you write your signature? I do it alot when I write C# code.

This is C style nomenclature typeing:
Static typeing

This is DHM typeing:
DHM typeing

Types are collection of things that belong to that set. Functions are mappnings from one type set to another.

Function mapping

A type definition of this function would look like:

1
2
3
4
5
//+ f :: (Shape, Color) -> Color
//The "(Shape, Color)" is a tuple. A tuple is like "typed list"
// of things. Where the number of things and the order of
// them matters.

A function can be viewed a set of rules to follow to get a value. But it can also be viewed as large lookup table that contains all the possible values. We looked at this in part 1 when we discussed function memoization.

Function composition in a type category

So when two functions are composed you can view this as two lookups. Or combine these two lookups into a single lookup table from X to Z.

Function composition

A javscript version of this could look like this:

1
2
3
4
5
6
7
8
9
//+ fg :: String -> String
var fg = {
"a": "@",
"b": "@",
"c": "#",
"d": "!!"
};
fg['c']; //"#"

Monoids

A monoid is a type class and a set of rules (methods on the monoid). And those rules obey associativity and identity (let call them metar ules). The most common example is clock arithmetic.
Let our type class be var numbers = _.range(0,11); and the rule be var rule = x => x % 12.

1
2
3
4
5
6
7
8
9
10
11
12
13
var numbers = _.range(0,11);
var rule = x => x % 12;
//Lets create our monoid! We call it Clock.
//+ Num -> Clock
var Clock = function Clock (x) {
this.value = rule(x);
};
//+ Clock -> Clock
Clock.prototype.add = function (y) {
return new Clock(this.value + y.value);
};

Is associativity met for Clock.add?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var x = Math.floor(Math.random()*4e15),
y = Math.floor(Math.random()*4e15),
a = new Clock(x);
b = new Clock(y);
c = new Clock(x+y);
//Then by associativity this will allways be true:
(a.add(b).value === c.value) && numbers.indexOf(c.value) > -1;
//This is the same as:
(rule(x+y) === rule(rule(x) + rule(y))) && numbers.indexOf(c.value) > -1;
//Or
((x+y)%12 === ((x%12) + (y%12))%12) && numbers.indexOf(c.value) > -1;

I won’t prove that modulo addition is associative but here is a proof for you sceptics.

Is identity met for Clock.add?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var e = 0, //Our neutral element.
x = Math.floor(Math.random()*4e15),
a = new Clock(x),
b = new Clock(e),
c = a.add(b);
//Always true
c.value === a.value;
//This is same as:
rule(x+0) === rule(rule(x) + rule(0));
rule(x) === rule(rule(x) + 0);
rule(x) === rule(rule(x)); //(x%12)%12 is same as just (x%12).
rule(x) === rule(x);

So we have shown that the meta rules are uphold for the add method inside our type numbers and our rule. So we have prooved that add with numbers and rule form a monoid.

So why complicate it? Because math, thats why!
If you have a monoid it is garantied with mathematical surety that you can’t fall outside the monoid by mistake.

It is like a guardrail for functions applied to types. You are garantied that the value is allways well defined within the specified type of the monoid.
Guardrail

The checking of associativity and identity should be implemented in the typechecker or compiler. And give the error before runtime to the programmer.

The monoid is a special case of a monad. Or rather a monad is a generalization of a monoid.

The next part in the series will be about functors and the ever so elusive monad.