A technical blog about programming and technology.

Monday, April 30, 2007

Coding in Haskell

Programming Language class is alot of fun (sometimes). I spent part of the weekend studying for exams and playing with haskell. I realized I missed one part of the assignment after I submitted, but it was an interesting formatting issue. What's most interesting about functional languages is how concise the code is for some complex problem. Consider the following problem:

I have a list of strings and I want to put an element o after every n elements in the list, then convert the list to one space delimited string.

Lets try to do it in C++ :

string insertEvery(int n, string o, vector<string> & vs) {
string res = "";
int pos = 0;
for(vector<string>::iterator it = vs.begin(); it != vs.end(); ++it) {
res += *it;
if(++pos % n == 0) {
res += " " + o + " ";
}
else {
res += " ";
}
}
return res;
}
Next up C# (Kind of a different approach):
string insertEvery(int n, string o, List<string> list) {		
for (int i = n; i < list.Count; i+=n) {
list.Insert( i++, o );
}
return string.Join( " ", list.ToArray() ).Replace( " " + o + " ", o );
}
And the winner...Haskell :
insertEvery n y [] = []
insertEvery n y x = (take n x) ++ [y] ++ insertEvery n y (drop n x)
insertEveryToString n y x = concat $ intersperse " " $ insertEvery n y x
I love the concise function definitions. Thinking totally recursive is hard at first, but once you get it everything just pieces together...

9 comments:

Michael Rywalt said...

hmmmm... small and concise, but try to do anything complex and it runs slower than C++ :)

Ok, ok, I know, I always have something to say :P . On the positive side, Haskell does allow the programmer the ability to link in code from other languages where certain algorithms are known to run faster. So yeah, I buy into the functional methodology using Haskell.. Cool language, and cool project!

Justin Dubs said...

In the Prelude:

unwords :: [String] -> String
unwords = concat . intersperse " "

Which makes your solutions:

insertEvery n o [] = []
insertEvery n o x = (take n x) ++ [o] ++ insertEvery n o (drop n x)
insertEveryToString n o x = unwords $ insertEvery n o x

And if you don't mind making it string specific:

insertEvery n o [] = ""
insertEvery n o x = unwords $ (take n x) ++ [o, insertEvery n o (drop n x)]

David Fowler said...

thats a very nice soln. i'm not quite the haskell pro as yet.

jag said...

Given the problem description, for n = 2 and o = "!" I'd expect the results for lists ["a", "b"] and ["a", "b", "c"] to be "a b !" and "a b ! c".

The Haskell code gives me "a b !" and "a b ! c !". (BTW, you might want to check the C++ and C# implementations, they differ too).

The following should implement the spec:

insertEvery n o xs | length chunk < n = chunk
                   | otherwise = chunk ++ o : (insertEvery n o (drop n xs))
                   where chunk = take n xs
insertEveryToString n o xs = unwords $ insertEvery n o xs

jag said...

BTW, how's this for concise:

string insertEveryToString3(int n, const string& o, const vector<string>& vs) {
  string res;
  for (vector<string>::size_type pos = 0; pos < vs.size(); ++pos)
    res += (pos != 0 ? " " : "") + vs[pos] + (pos % n == n - 1 ? " " + o : "");
  return res;
}

Clearly not the most efficient (all those string objects being created), but not much worse than the Haskell example in terms of readability, if you're familiar with certain idioms.

BTW, if I'd made res an out-var instead, that'd drop two more lines from that version (I could assume the string was empty to begin with, or clear it as part of pos's initialization using the comma operator).

David Fowler said...

The disambiuation between ["a","b","!","c","!"] and ["a","b","!","c"] is fine but for my purposes either way will do. My point was to show that no matter how concise you make the c++,c# or code written in any imperitive language for that matter, it will never be as readable as the haskell version. Thats the beauty of referential transparency...

BTW i fixed the C++ version for you :D

jag said...

The fixed version looks exactly like the one I C&P-ed into this comment field. I must've screwed something up when I changed the &s, <s and >s. Thanks for fixing it!

Now, maybe it's because I mostly work in C++-like languages, but I don't find the Haskell version more (or less) readable than my C++ version. If there was a separate need for insertEvery() I would write insertEveryToString(...) as join(" ", insertEvery(n, o, vs)) which is IMO just as readable as the Haskell version.

Then you could argue that the C++ version of insertEvery(...) is harder to read because looping through your vector to copy it and insert element o every n-th step is harder to grasp than taking the first n elements plus element o plus the_same_applied_to_the_rest, but I just don't see that.

That said, there are cases where it's easier to express (and understand!) things in Haskell than it is in C++ and other imperative languages. I just don't think your example makes a very good one. But then again, maybe that's just me :-)

Michael said...

Checkout out Data.List (intercalate).

intercalate = concat . intersperse

Anonymous said...

Opulently I assent to but I think the post should have more info then it has.