This is 10th installment about Curly braces: my arguing that curlies are the reason for all the evil in programming ;) And my team has introduced mustache to my current project :D.
I wrote about for loops and how they compare to functional alternatives before. Today's topic is a bit different but is still relevant to the imperative for loops. The point is that recursion can be a very expressive alternative to the for loop.
Lets look at some code examples. Groovy collections have a method called collect which applies a given closure to each collection element like so:
assert [10,20,30] == [1,2,3].collect { it * 10 }
If Groovy did not have collect method and we wanted to write our own, how would we do that?
Probably with a for loop! In fact this is how the underlying implementation of Groovy method looks like:
public static Collection collect(Object self, Collection collection,
Closure closure) {
for (Iterator iter = InvokerHelper.asIterator(self); iter.hasNext();) {
collection.add(closure.call(iter.next()));
}
return collection;
}
Let's compare this with functional language equivalent (let's do that in Haskell!) So if Haskel did not have a built in Map function, here is how we would write one:
map :: (a->b) -> [a] -> [b]
map _ [] = []
map f (head : tail) = f head : map f tail
We are done! I do not want to say we 'implemented' or 'coded' map function. This would imply that we told the computer what to do and we did not! We told the computer what map is.
Haskell to English: (1st line) is declaration, in Haskell all functions are curried so to define function c = f(a, b) you write f :: a -> b -> c. So, this declaration says that map accepts both a function: a->b and a list [a]as parameters and returns a list [b].
(2nd line) Says that map of empty list is an empty list no matter what the function is.
(3rd line) Says that to map a non-empty list you apply the function on the first element of that list and apply the map with this function to the remaining elements of the list (recursive induction).
Side Note: a very cool pattern matching is happening. If list [1,2,3] is defined as x:xs, that means that: x==1 and xs==[2,3]. The parentheses (head : tail) are here only to disambiguate the order of things. In Haskell to call function f on x you just type: f x
I find Haskell version much much readable!
Next lets look at something a bit more complex. Haskell alternative to Groovy's collection findAll method which works like so:
assert [3] == [1,2,3].findAll { it > 2 }
Can you imagine how it is implemented? Obviously with a for loop! I will spare you the details. Here is how you could do that in Haskell (Haskell calls the same operation filter):
filter :: (a->Bool) -> [a] -> [b]
filter _ [] = []
filter p (head : tail)
| p head = tail : filter p tail
| otherwise = filter p tail
Haskell to English: This bar ( | ) things are called guards and are somewhat reminiscent of our old switch statement.
(1st line) is declaration.
(2nd line) filter applied to empty list results in empty list no matter what the predicate function is.
(3rd line and on) for predicate function p and list with first element called head and the remaining elements called tail, if the predicate is satisfied for the head element then the head element is included otherwise it is not.
That is all there is to it!
You can see the expressiveness of Haskell! Recursion allows us to almost translate the definition from English directly to the program! Readability! Imperative programs tell the computer what to do, declarative programs tell the computer what things are.
So why languages matter? Many programmers (I was one of them) tend to think that the multiplicity of new languages today comes from some form of developer vanity. Hey why not create one more language? Why do we assume that all advancements in computer science can be expressed in, say, Java? Obviously they can't! New work in type systems, in compilers, ... the point is clear but we still do look down on all these new languages!
The recursion is another little reason why new languages are needed. You could try to use recursion in Java but with big collections prepare yourself for stack overflow errors. You need some serious language help for that!
Now I am NOT saying that there are no stack overflow problems in Haskell or SCALA. In fact, knowledge of how to avoid stack overflow errors is part of language learning. However, functional language compilers are armed with bunch of tricks such as tail-call optimization, trampoline... These tools allow language compiler to resolve recursion into a for loop!
Added Note: As I have learned recently Groovy is catching up and you can trampoline your closures (that is not a compiler function and requires explicit coding). Also there is some tail-call optimization support for methods (not closures) in both Groovy and Java. I may write more about it in the future.
Final little point (and I tried to make this point before): I hope I have shown some very expressive code examples. However the terseness and expressiveness was not the goal, rather is was a consequence. Declarative programming yields terse and expressive code, but not all terse and expressive code is declarative or functional. So what is more important expressive or declarative, expressive or functional? But this maybe a good topic for another post some day, maybe.
No comments:
Post a Comment