Efficiency

At the moment, I’m taking a class in Combinatorial Algorithms. You can probably gather from the things that I write about here that this is not my passion… however so far it’s better than expected. We’re moving onto backtracking. If you know a functional language such as Haskell or ML (I know there are others, these are just the two I know) backtracking is fairly easy, so of course I ask if we can use such a functional language for our assignment. So then this exchange happens (of course I Twittered it):

Student: Why are you talking about functional programming?

Professor: Oh… she’s European.

Ah yes, we Europeans like to sit in cafe’s drinking espresso and talking about politics, philosophy, functional programming…

For our current assignment, one of the questions was to write a program that would produce all the “derangements” for a given number: a derangement is like a permutation except none of the elements are in the original position (see the table at the end of the post). There are fewer than 6 students in the class and two of them mentioned to me that they found this question difficult. However I wrote it in Haskell, and it took me 8 lines of code and 2 hours (the first chunk of which was spent getting to grips with the syntax again – it’s been a while) and runs really fast. See below:

Note – I’m not concerned about putting this up before I’ve handed it in, as there are very few students in the class and I’m confident none of the others know Haskell

-- Cate Huston - Question 3

import Data.List

derange :: Int -> [[Int]]
derange n = iter (n-1) (permutations (makeList n))

makeList :: Int -> [Int]
makeList 0 = []
makeList n = makeList (n-1) ++ [n]

iter :: Int -> [[Int]] -> [[Int]]
iter 0 ls = remove 0 ls
iter a ls = iter (a-1) (remove a ls)

remove :: Int -> [[Int]] -> [[Int]]
remove _ [] = []
remove a (l:ls) = if (l!!(a) == (a+1)) then remove a ls
                  else l : (remove a ls)

This code is efficient, in the sense that it didn’t take me very long, but it’s also very efficient to run because of the way Haskell uses lazy evaluation, so things are not created (or computed) until it’s necessary. So even though it looks, for instance, that creating a list of permutations is one of the first things I’m doing, in practice it’s something that happens very shortly before the relevant permutation does (or doesn’t) appear on my screen.

Computer Science (or Informatics) at the University of Edinburgh wasn’t always the most fun experience but here’s what I’m grateful for: I’ve programmed in 9 languages. And whilst I’m not particularly confident in all of them, I know enough about each of them to have an appreciation for when it’s appropriate. I think Haskell is most appropriate in this instance, for example, but I’m using Java for my visualizations. If I need to script something, I’ll probably use Python and I understand why C is still used a lot, but also why it’s difficult to code in (and so very, very difficult to teach a beginner). The only thing I still don’t get is Tcl (everything’s a String! Everything! Why?).

This makes me more efficient as a programmer, in that I have more choice to fine the best language for what I’m doing, and also in that I’m not afraid to learn another language and I don’t get fazed by the syntax being different. Yesterday, for example, I debugged someone’s Visual Basic code. I’ve not really done any VB before (since 2004 I’ve only used Windows when someone’s paid me to), but type errors are type errors so it didn’t take long to fix.

Programmers – we need to stop clinging to the one language we know (primarily Java, I’ve found) and thinking we can do everything in it. It’s probably possible, but there might be a better way. And in 10 years time, will Java still be this popular or will something have surpassed it? We need to have the skills to move on, if the need arises.

Derangements – all of these (and 7 – not shown) ran in well under 1s