I recently uploaded my first NuGet package. It contains my first shot at playing with functional programming with my favorite computer language. This has been inspired by the things I’ve learned in the book Functional JavaScript.
Thinking from a functional programming standpoint is quite different than traditional OOP thinking. Sometimes I call it ‘inside-out thinking’. It can lead to some seriously efficient code. You’ll see that with a powerful tested functional library, you end up writing less code; and the less code you write, the less code you have to test, and the less code that can go wrong. Remember that you can probably write a 5 line program that has no bugs. I recall seeing my college Lisp instructor code faster and more powerfully than any C coder I’ve ever met. To be sure, there are a lot of good functional languages to learn these techniques, among them Clojure, F Sharp, and Nemerle. As a C Sharp guy, I’ll start with a library, and apply functional programming to my C sharp code. You can see much of the influence of functional programming when exploring LINQ. I’ll be using some of the LINQ extensions in my library.
Sometimes I write code like this:
or this:
for(int i=0;i < 5; i++) result.Add(fn(i));
Let’s do this from a functional standpoint. We’ll build with bricks. One of the first things I've discovered is the conflict between operators and functions. I can pass around functions, but I can't pass around operators. Thus, we'll make the operators in to functions. Here are some bricks:
public static Func<int, int, bool> gt = (l, r) => (l > r);
public static Func<int, int, bool> lt = (l, r) => (l < r);
public static Func<int, int, bool> equ = (l, r) => (l == r);
public static Func<int, int, bool> neq = (l, r) => (l != r);
// many more are not displayed here
:
}
One of the takeaways from functional programming is the increasingly blurry line between code and data. You may see the term “code = data”. Note that these are almost the same thing:
IEnumerable<int> x2() { for(int i = 0; i < 5; i++) yield return i; }
These are not completely interchangeable, as we can declare the list implementation in a function, but not the function implementation. Had we been able to have a yield return in a lambda, we could have. We’ll make another brick.
int step = ((end - start) > 0) ? 1 : -1;
for (int i = start; neq(i, end); i += step) yield return i;
}
The full-featured version would be:
int Step = ((end - start) > 0) ? Math.Abs(step) : -Math.Abs(step);
Func<int, int, bool> condition = ((end - start) > 0) ? lt : gt;
for (int i = start; condition(i, end); i += Step) yield return i;
}
Code = data, replacing a list of integers with a range. Now these are the same:
IEnumerable<int> x2 = Functional<int>.range(0,5,1);
Functional programming promotes recursion over iteration. Often one will build a function that takes a list, and does something with the first element, and the then calls itself with the rest of the list, recursively. Therefore a couple useful functions are to get the first element of a list, and a function to return the rest of the list. I use some LINQ functions for this.
public static Func<IEnumerable<T>,IEnumerable<T>> rest = (lst) => lst.Skip(1);
Back to my original code, these bricks:
public static IEnumerable<U> map<U>(IEnumerable<T> lst, Func<T, U> fn) { return lst.Select(fn); }
make this:
becomes:
And this:
IList<int> result = new List<int>();
for(int i=0;i < 5; i++) result.Add(fn(i));
becomes:
Another couple of bricks are:
public static T reduce(IEnumerable<T> lst, Func<T, T, T> acc, T initialItem) {
return lst.Aggregate(initialItem, acc);
}
Now suppose we had a string “abcdefg”, and we want to transform that to “a.b.c.d.e.f.g”. In the old days, I might do this:
string result = source[0].ToString();
for(int i=1; i<source.Length;i++) {
result = result + c.ToString() + source[i].ToString();
}
return result;
}
Now I depend on a functional style:
IEnumerable<char> seq = Functional<string>.Chars(s);
string result = Functional<char>.reduce<string>(
Functional<char>.rest(seq),
(st, ch) => st + c + ch,
Functional<char>.first(seq).ToString()
);
return result;
};
It’s often useful to know if two sequences are the same. I have a function that does this, and is very useful in my tests.
IEnumerator<T> i1 = lst1.GetEnumerator();
IEnumerator<T> i2 = lst2.GetEnumerator();
bool result = true;
bool b1 = i1.MoveNext();
bool b2 = i2.MoveNext();
while (result && (b1 && b2)) {
result = fn(i1.Current, i2.Current);
b1 = i1.MoveNext();
b2 = i2.MoveNext();
}
return (result && (b1 == b2));
};
With this I can verify that:
bool success = Functional<int>.same(result, Functional<int>.range(0 + 5, 7 + 5),Functional<int>.equ);
There is a strange function called always. Sometimes it's useful to have a function that always return a specific value.
Interestingly, making two functions with the same value, does not return the same function.
Func<int> y = Functional<int>.always(3);
// x != y
Just to tighten the potential proliferation of functions a bit, I provide the alwaysTrue and alwaysFalse functions:
public static Func<Func<bool>> alwaysTrue = () => () => true;
public static Func<Func<bool>> alwaysFalse = () => () => false;
There are times where it's useful to combine two or more sequences in some way, and return the new sequence.
IEnumerator<T> one = lst1.GetEnumerator();
IEnumerator<T> two = lst2.GetEnumerator();
while ((one.MoveNext()) && (two.MoveNext())) {
yield return fn(one.Current, two.Current);
}
}
So testing the three sequence of this would be painful without the sequence compare function called same. We'll start with this brick:
Now to test the three-sequence combiner.
// t f f t
IEnumerable<Func<bool>> test = new List<Func<bool>>() {
Functional<bool>.always(true),
Functional<bool>.always(false),
Functional<bool>.always(false),
Functional<bool>.always(true)
};
IEnumerable<char> first = Functional<string>.Chars("xoxo");
IEnumerable<char> second = Functional<string>.Chars("xxoo");
IEnumerable<char> third = Functional<string>.Chars("xooo");
IEnumerable<Func<bool>> result = Functional<char>.map<Func<bool>>(first, second, third,
(x, y, z) => Functional<bool>.always(Functional<bool>.and((x == y), (y == z))));
success = Functional<Func<bool>>.same(result, test,(x,y)=>x()==y());
The key is passing a function that knows how to compare elements of the sequences. The == operator fails this, so the functional style of passing functions to functions saves us.
Finally, I have some curry functions. This is a technique to creating a function on the fly, and also configuring it. Suppose that I have a function that can add two integers (as I do)
Now suppose that we need a function that takes an integer, and returns the sum of that integer, and 6. In the recent past, I would be tempted to write:
No more. I have a class called Curry2 (big brother to Curry1) that takes a function, and when asked, will return a configured function.
private Func<T, U, U> fn; // U fn(T t, U u)
public Curry2(Func<T, U, U> fun) { this.fn = fun; }
public Func<U, U> Create(T t) { return (x) => this.fn(t, x); }
}
Creating the addSix function looks like this:
Func<int, int> addSix = add.Create(6);
int r = addSix(21); // 27
I’ve published version 0.0.9 here. Install it and try it out.
No comments:
Post a Comment