How to Code With No Loops
Functional Programming and Haskell
Let's continue on the functional programming journey this week. One of the biggest things that scared me about learning Haskell and Functional Programming was that I had heard that they don't use loops. No loops!? That's crazy, I code with loops left, right, and center. What do you mean there are no loops? It's such a basic fundamental tool. Also, why don't we use them? What do you do instead? This was very overwhelming as you can see. Below I’ll summarize my understanding of why functional programming languages usually emphasize the use of recursion (or higher-order functions) over loops and show a few examples. Hopefully, it'll all be a little less scary after this.
What does a loop do exactly?
Before we leave loops behind, let's try to understand what we need(ed) them for. Loops are used to control flow. In imperative languages, we use loops to do a task a certain number of times. Loops are used for iterations. Sometimes we know how many iterations we will need, sometimes we don't. But, we do know the code in the loop could run more than once.
Do we ever NEED a loop? No, not really. What you may need is a way to do a certain task a number of times, or iteration. And you can use a loop for that, but this can also be done in other ways, (ie recursion).
Why doesn't functional programming use loops?
Even if we don't have to use loops, why does functional programming not like them?
- Pure Functions
What's the first thing we remember about functional programming? Oh right, it focuses on using pure functions and doesn't like side effects. Let's take a look at this loop below:
sum = 0
for(let num of arr) sum += num
Now let's look at the loop. the loop unfortunately is not side-effect-free. In fact, loops rely on side effects to control flow. Something has to change for you to exit your loop. In the example above, the side effect is being caused by the assignment statement
sum += num . Assignment statements are not side-effect-free since they modify the state. So even though the function is pure, the loop isn't. A loop is not pure. And Haskell, being a purely functional programming language, doesn't like this and doesn't allow for it.
Not only is a loop not pure, but neither are variables. They can change and are mutable. Loops usually require variables, like a counter (so much impurity!). Purely functional programming languages, like Haskell, don't (by default anyway) provide ways to mutate a value, like a counter or a pointer. By default, variables are not mutable cells. Which in turn doesn't allow for loops.
2. Declarative Not Imperative
The second big characteristic of functional programming is that is declarative, not imperative. We aren't so focused on how something is being done but rather what. The best example of this difference I found in the answer to this Quora question: Why doesn’t Haskell have loops (e.g. for or while)? Here is my summary of the answer: Say you wanted to go through a long list of numbers and return all the even ones.
In imperative, I would tell you the steps. First, take the first number in the list. Then divide by two. Then check the remainder. Do something if the remainder is 0. Then move on to the next number, etc etc. It's a loop and I tell you the steps in the loop.
In declarative programming, I simply say, give me all the even numbers and I define even numbers as being one where if you divide it by 2 you get 0. That's it. I'm not telling you how to find out if a number is even. I'm simply defining it.
Ok, but how is the computer going to “give me all the even numbers”? It will need a loop anyway. You are right, it will. But that's not what I, the functional programmer, is focused on. I'm not writing out steps or subsequent operations, I'm only expressing a set of facts. So yes, the compiler may still need loops, but I won't.
So what do we do with no loops?
Programs will need iterations. So without the traditional for, while, or do loops, Haskell focuses on recursion and higher-order functions (which use recursion under the hood).
Recursion is a flexible way to do iterations in Haskell. Loops repeat code, recursion repeats the call to the function. Makes sense that they can be used interchangeably. Here is an example of a function that prints “hello world” n times:
printNTimes 0 = return ()
printNTimes n =
putStrLn "hello world"
For the base case of n=0, we print nothing, otherwise, we print the string and call the function recursively with a decremented n as the argument. Another example: we want to square each element of an array (or list in Haskell):
allSquares :: Num a => [a] -> [a]
allSquares  = 
allSquares (x : xs) = x * x : allSquares xs
So again we have the base case where an empty list returns an empty list, otherwise, we separate the list into its head
x and tail
xs. Then we build a new list, with
x * x as the head, and the result of the recursive call with the tail
xs as the argument.
In Haskell, functions can take functions as parameters and return functions. This is called a higher-order function. They are especially handy for iterating. By using higher-order functions to iterate over collections, we produce more readable code with fewer chances of errors (for example no out-of-bounds error). Some useful ones include:
map: used to transform each element of a collection. It won't change the type or length of your collection.
Example- If you wanted to print out the values from 1 to 20:
let xs = [1..20]
mapM_ print xs
filter: used to return elements of a collection that meet certain criteria. This new subset can be of a different length than the original collection.
Example- To filter out all words in a list that start with the letter ‘a’:
beginsWithA (c:_) = c == 'a'
beginsWithA _ = False
myStringFilter xs = filter (not . beginsWithA) (map tail xs)
fold: used to accumulate, aggregate, or reduce a collection to a return value
Example- Let’s implement the sumArray function using fold:
sumArray :: Num a => [a] -> a
sumArray xs = foldl (\acc x -> acc + x) 0 xs
Note: In researching this blog I found references to some “for-loops” that can be used in Haskell and they are called