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?

  1. 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:

sumArray(arr) {     
sum = 0
for(let num of arr) sum += num
return sum
}

We used a loop here (javascript for-of loop) to determine the sum of the elements in an array. Nothing fancy at all. Looks pretty safe to me too, for the same array we will get the same sum so the function sumArray looks pure to me.

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

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 =
do
putStrLn "hello world"
printNTimes (n-1)

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.

Higher-Order Functions

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:

do
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 for and for_.

References

I love seafood, exploring new cities, board games and learning to love to code. https://github.com/sarakhandaker/portfolio

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store