That’s true: the last post was exactly 5 months ago, but I’m still alive! A lot of new stuff happened during these 5 months. Two days after writing the last post, I went with my group (Foundations of Programming) to a very nice hotel in Ruddington, where, during two days, each member had to present something about his/her work. I’ve talked about a result I’ve derived related with distributivity through the Greatest Common Divisor. My slides are available at the event’s webpage and I will put online a note with all the details.
A few days later Alexandra got ill with some strange pain in the abdominal area. The following weeks were really hard, since she had to go to the hospital emergency services. So that you have an idea of how strange the whole thing was, the doctors still don’t know what the problem is! Now, she has occasional pain, but it seems to be much more controlled.
Anyway, more or less at the same time I started to read a very nice article (a Functional Pearl) written by Jeremy Gibbons, Richard Bird and David Lester named “Enumerating the Rationals“. The paper presents some algorithms encoded in Haskell to enumerate the positive rational numbers. In particular, it presents algorithms to construct the famous Stern-Brocot and Calkin-Wilf trees. It also presents a very efficient algorithm to enumerate the rationals in Calkin-Wilf order just by using as current state the previous rational (i.e., two integer numbers). However, the authors claim that “it is not at all obvious” how to create a similar efficient algorithm for enumerating the rationals in Stern-Brocot order. Well, after reading it, Roland (my supervisor) and me found a way of doing it. The key idea is that rational numbers are pairs of coprime numbers (numbers which greatest common divisor is 1) and thus, we can use Euclid’s algorithm as a basis for enumerating these pairs. By using the Extended Euclid’s algorithm written using matrix multiplication, we were able to derive both Calkin-Wilf and Stern-Brocot enumerations from the same algorithm. We wrote a paper named “Recounting the Rationals: Twice!” that was submitted to the journal American Mathematical Monthly.
I’ve also presented the algorithm at the “Fun in the Afternoon” event in Cambridge, last May. I think the talk was clear enough and, although it has nothing to do with functional programming, its methodological aspect should be interesting enough to any (functional) programmer. I’ve had very positive feedback on the talk, which is a good sign. The slides of the talk are available in the event’s webpage.
In April I’ve attended to the Midlands Graduate School (MGS Spring School). It was a very nice event organised by our group (in particular, I have to congratulate Henrik and Graham for their excellent work!) with very nice talks as well. My favourite courses were Category Theory, Algorithmic Problem Solving and Operational Semantics, but I’ve also enjoyed the others I’ve attended. The best thing about this kind of event is the social interaction that you have with other students and researchers. And again, as happened before in other similar events, I always get that cold sensation that I don’t know nothing about anything! The good news is that this feeling is a constructive one, since I get motivated to learn more!
And since we’re talking about learning, I’m currently studying Generating Functions, which are formal power series that encode information about sequences. Generating Functions are a very powerful tool: they can be used to prove identities very easily, to find nice and closed formulas to recurrence relations, to work with datatypes in order to find isomorphisms and, more importantly to my work, they can be used to solve counting problems in a very effective way. I’m writing a note about what I’m learning and I’ll probably post it here.
To finish the news about work, I’m currently preparing two JFFs (JFFs are my personal technical notes). The first one deals with the very known and simple problem that consists in swapping the value of two variables without using another temporary one. The second shows how to construct a very famous algorithm. I promise that I will post the notes here, as soon as they are available!
Besides work, I guess that the only relevant thing to talk about is that we went on holidays to Halkidiki in Greece in the last week of May. It was excellent and Alexandra and me will post a somewhat detailed description on our joint blog Furiousmind.org.
- Post JFF0, JFF1 and JFF2 (these are the notes on distributivity and the greatest common divisor, how to swap values of variables without using another temporary one and the construction of an algorithm that is well-known, respectively);
- Prepare a note I have written together with my supervisor about Number Theory to be distributed;
- Prepare things to the Summer School in Marktoberdorf (Formal Logical Methods for System Security and Correctness). It’s true! I’ve been accepted to participate in the school and I already got the plane tickets. This means that I’ll be in Germany from the 31st July to the 12th August. Then I fly directly to Portugal and I return to Nottingham on the 29th August. So, if you want something from Germany or Portugal, let me know
- Since I’m talking about trips, Alexandra and me are going to Amsterdam this next weekend. We’re really looking forward for it! And if you want something from there, please let us know.
Thanks for reading and see you in the next post!