Comparison between for loops and pattern matching

A common problem many beginners in functional programming have is that, at first glance, we lost the ability to do for loops. This blog post will showcase a number of for loops and compare them with their functional counterpart.

Iterating through a collection

I'm sure most of you have met something like the following form before:

for x in xs:
    update_state(state, x)
return state;

It's often built on top of iterators, let's "desugar" it step by step. I will use Java here:

for (Foo x: collectionOfFoo)
    do_something_with(state, x);
return state;

// into
var iter = collectionOfFoo.iterator();
while (iter.hasNext()) {
    var x = iter.peek();
    do_something_with(state, x);
    iter.next();
}
return state;

Not as nice looking!

Notice in each iteration, we are updating the state, and we are given an iterator that can either be empty or has a head. We then "reduce" the iterator by striping its head until it's empty. We do the exact same thing in Haskell:

-- "break" case
traverse_collection []     state     = state

-- execute the body and "go to next iteration"
traverse_collection iter state       = traverse_collection (tail iter) (do_something_with state (head iter))

-- with pattern matching
-- traverse_collection (x:xs) state  = traverse_collection xs (do_something_with state x)

Note how the do_something_with is the same, but the "goto" part implied by the while loop is done via recursion.

The Haskell version's pattern matching also includes how to "get next item from iterator", as most Haskell data structures are inherently recursive. In this case this part of logic is not shown in the Java version, which would make the Java example even more verbose.

This is encapsulated as foldl, Java enhanced for loop works on Iterables, and likewise, foldl works on Foldable.

Do something x times

Let's look at "do something x times" kind of loop, this is probably missed the most, but as we are about to see, the imperative version is very verbose and lacks sugar like in the iteration case above.

int fib(int n) {
    int x = 1;
    int y = 1;
    for (int i = 0; i < n - 1; i++) {
        int tmp = y;
        y += x;
        x = tmp;
    }
    return y;
}

We shall see that we can have a tail-recursive version in Haskell that does the same thing, but is much shorter.

fib n = fib' 0 1 n
    where
        fib' _ y 0 = y
        fib' x y n' = fib' y (x + y) (n' - 1)

Indexed for loop

for (int i = 0; i < xs.length; i++)
    do_something_with(i, xs[i], state)

In the Haskell version we can reuse our traverse_collection.

-- define new do_something_with function that does something with the index

f xs state = traverse_collection (zip xs [1..]) state

Notice how the imperative version needs a bit more code when it lost the iterator sugar, but the functional version stayed mostly the same. (And of course a fold would be much more convenient here)

You can still use an enhanced for loop if you use the stream api, but that's borrowed from functional languages anyway 😃.

Example: split text by white space

Java:

List<String> split(String input) {
    var state = new ArrayList<String>();
    state.add("");
    for (char c: input.toCharArray()) {
        if (c == ' ') {
            state.add("");
        } else {
            var index = state.size() - 1;
            state.set(index, state.get(index) + c);
        }
    }
    return state;
}

// split("Hello Functional Programming");
// ==> [Hello, Functional, Programming]

Haskell:

split :: String -> [String]
split str = reverse (split' str [""])
    where
        split' :: String -> [String] -> [String]
        split' [] ss = ss
        split' (x:xs) ss@(h:t)
            | x == ' ' = split' xs ("" : ss)
            | otherwise = split' xs ((h ++ [x]):t)

-- λ ->  split "Hello Functional Programming"
-- ["Hello", "Functional", "Programming"]

Version without reverse that looks even more like the java version

split :: String -> [String]
split str = split' str [""]
    where
        split' :: String -> [String] -> [String]
        split' [] ss = ss
        split' (x:xs) ss
            | x == ' ' = split' xs (ss `snoc` "")
            | otherwise = split' xs (changeLast ss (last ss `snoc` x))

        -- they are available in various places but I will put them here for reference
        snoc xs x = xs ++ [x]
        changeLast xs x = init xs ++ [x]

-- λ ->  split "Hello Functional Programming"
-- ["Hello", "Functional", "Programming"]