Yeah, yeah - Haskell's weird. It's a programming language without loops, whose variables can't be updated, and with which you can't (unless you grok the concept of monads) even do I/O! Well, forget all those things, because you really don't need them. Don't believe me? The next generation of the Perl language, Perl6, might be written in Haskell (http://www.pugscode.org/). See? Totally useful.

Loops

I've gotten this question several times now, where you're given a piece of pseudocode to implement in Haskell that uses a loop to iterate over some piece of data (like a for loop from 0 to N). Let's suppose your pseudocode looked like this:

x = <list of numbers>
result = false
for each element i in X:
    if i < 0:
        result = true

Basically, we're just walking through a list and checking to see if any elements are less than zero. But how do we do this in Haskell, when we can't loop through the list? Recursion!

is_negative [] = False
is_negative (x:xs) = (x < 0) || (is_negative xs)

(Of course, if you're clever you could re-write this function using map and fold, but that wouldn't illustrate recursion very well, would it? Let me make my point here...)

Let's step through this (trivial, contrived) example. First we define a base case for recursion; an empty list clearly contains no negative numbers, so (is_negative []) should return False. If it's not an empty list, test whether the first element is less than zero and OR that against the function recursively applied to the rest of the list. As it's evaluated this code turns into something like this:

(is_negative [2,-1,3])
(2 < 0) || (is_negative [-1,3])
(2 < 0) || (-1 < 0) || (is_negative [3])
(2 < 0) || (-1 < 0) || (3 < 0) || (is_negative [])
(2 < 0) || (-1 < 0) || (3 < 0) || False
(2 < 0) || (-1 < 0) || False || False
(2 < 0) || True || False || False
False || True || False || False
True || False || False
True || False
True

The key to writing Haskell code is to stop thinking about variables and loops, and start thinking in terms of lists and what operations you actually need to apply to their elements. -- TrevorFountain - 18 Feb 2009

Topic revision: r1 - 18 Feb 2009 - 17:45:56 - TrevorFountain
 
This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback
This Wiki uses Cookies