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