Looping in Haskell

When I first started out with Haskell, some things were made very clear: it was a pure language, it was expressive, and it told what data was, not what it did. However, coming from imperative languages like Java and C, I found myself wanting to know how to loop in Haskell. This was a basic want, because looping is one of the big concepts in programming those languages (along with conditionals and blocking). So, here are some correct ways to "loop" in Haskell, using higher-order functions and recursion.


Tail Call Recursion
Tail Call Recursion is a particularly efficient method of traversing data. The basic structure of a tail-recursive function is:

1. Check the base-case
2. Perform some action
3. Set up the tail call.

The base case is what happens when you no longer want to recurse. If you're moving over a list of Ints, adding 1 to everything, this could be when the list is [] (empty).

In this case, the action would be adding one to a value, and appending it to the next call of the function.

The tail-call would then be the same function, but with the head of the list cut off.

The add-one-to-all numbers function would look something like this:

add-one-to-all :: [Int] -> [Int]
add-one-to-all [] = []
add-one-to-all (x:xs) = 1 + x : add-one-to-all xs

Here, when the list pattern matches [] (an empty list), an empty list is returned. Only when this happens will the function "snap back", collecting the other values from the list.

Higher-Order Functions
The entire point of a higher-order function is to be able to pass functions as parameters to other functions, or to return them from functions. In traversing a list, for instance, you could make a function that takes a function and a list, and then apply that with a function that adds one to a number.

traverse :: (a -> b) -> [a] -> [b]
traverse _ [] = []
traverse f (x:xs) = f x : traverse xs

add-one :: Int -> Int
add-one x = x + 1

add-one-to-all :: [Int] -> [Int]
add-one-to-all x = traverse add-one x

Here, you can see that the function "f" of traverse (type: (a -> b)) is applied recursively to a list. a and b are just type parameters, which are helpful for generic abstractions like this. Then, add-one is defined, and finally mapped over the list in add-one-to-all. The function "traverse" actually already exists in Prelude as the function map.

A bit extra
Haskell does something called currying, which allows the partial application of functions. Discussion on currying is outside the scope of this simple tutorial, but here is a very small implementation of add-one-to-all

add-one-to-all :: [Int] -> [Int]
add-one-to-all = map (+1)