transferring an imperative for-loop into idiomatic haskell

Question

I have some difficulties to transfer imperative algorithms into a functional style. The main concept that I cannot wrap my head around is how to fill sequences with values according to their position in the sequence. How would an idiomatic solution for the following algorithm look in Haskell?

A = unsigned char[256]
idx <- 1
for(i = 0 to 255)
    if (some_condition(i))
        A[i] <- idx
        idx++
    else
        A[i] = 0;

The algorithm basically creates a lookup table for the mapping function of a histogram.

Do you know any resources which would help me to understand this kind of problem better?

Answer 1

One of the core ideas in functional programming is to express algorithms as data transformations. In a lazy language like Haskell, we can even go a step further and think of lazy data structures as reified computations. In a very real sense, Haskell's lists are more like loops than normal linked lists: they can be calculated incrementally and don't have to exist in memory all at once. At the same time, we still get many of the advantages of having a data type like that ability to pass it around and inspect it with pattern matching.

With this in mind, the "trick" for expressing a for-loop with an index is to create a list of all the values it can take. Your example is probably the simplest case: i takes all the values from 0 to 255, so we can use Haskell's built-in notation for ranges:

[0..255]

At a high level, this is Haskell's equivalent of for (i = 0 to 255); we can then execute the actual logic in the loop by traversing this list either by a recursive function or a higher-order function from the standard library. (The second option is highly preferred.)

This particular logic is a good fit for a fold. A fold lets us take in a list item by item and build up a result of some sort. At each step, we get a list item and the value of our built-up result so far. In this particular case, we want to process the list from left to right while incrementing an index, so we can use foldl; the one tricky part is that it will produce the list backwards.

Here's the type of foldl:

foldl :: (b -> a -> b) -> b -> [a] -> b

So our function takes in our intermediate value and a list element and produces an updated intermediate value. Since we're constructing a list and keeping track of an index, our intermediate value will be a pair that contains both. Then, once we have the final result, we can ignore the idx value and reverse the final list we get:

a = let (result, _) = foldl step ([], 1) [0..255] in reverse result
  where step (a, idx) i
          | someCondition i = (idx:a, idx + 1)
          | otherwise       = (0:a, idx)

In fact, the pattern of transforming a list while keeping track of some intermediate state (idx in this case) is common enough so that it has a function of its own in terms of the State type. The core abstraction is a bit more involved (read through ["You Could Have Invented Monads"][you] for a great introduction), but the resulting code is actually quite pleasant to read (except for the imports, I guess :P):

import Control.Applicative
import Control.Monad 
import Control.Monad.State

a = evalState (mapM step [0..255]) 1
  where step i
          | someCondition i = get <* modify (+ 1)
          | otherwise       = return 0

The idea is that we map over [0..255] while keeping track of some state (the value of idx) in the background. evalState is how we put all the plumbing together and just get our final result. The step function is applied to each input list element and can also access or modify the state.

The first case of the step function is interesting. The <* operator tells it to do the thing on the left first, the thing on the right second but return the value on the left. This lets us get the current state, increment it but still return the value we got before it was incremented. The fact that our notion of state is a first-class entity and we can have library functions like <* is very powerful—I've found this particular idiom really useful for traversing trees, and other similar idioms have been quite useful for other code.

Answer 2

There are several ways to approach this problem depending on what data structure you want to use. The simplest one would probably be with lists and the basic functions available in Prelude:

a = go 1 [] [0..255]
    where
        go idx out [] = out
        go idx out (i:is) =
            if condition i
                then go (idx + 1) (out ++ [idx]) is
                else go idx (out ++ [0]) is

This uses the worker pattern with two accumulators, idx and out, and it traverses down the last parameter until no more elements are left, then returns out. This could certainly be converted into a fold of some sort, but in any case it won't be very efficient, appending items to a list with ++ is very inefficient. You could make it better by using idx : out and 0 : out, then using reverse on the output of go, but it still isn't an ideal solution.

Another solution might be to use the State monad:

a = flip runState 1 $ forM [0..255] $ \i -> do
        idx <- get
        if condition i
            then do
                put $ idx + 1    -- idx++
                return idx       -- A[i] = idx
            else return 0

Which certainly looks a lot more imperative. The 1 in flip runState 1 is indicating that your initial state is idx = 1, then you use forM (which looks like a for loop but really isn't) over [0..255], the loop variable is i, and then it's just a matter of implementing the rest of the logic.

If you want to go a lot more advanced you could use the StateT and ST monads to have an actual mutable array with a state at the same time. The explanation of how this works is far beyond the scope of this answer, though:

import Control.Monad.State
import Control.Monad.ST
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as MV


a :: V.Vector Int
a = runST $ (V.freeze =<<) $ flip evalStateT (1 :: Int) $ do
    a' <- lift $ MV.new 256
    lift $ MV.set a' 0
    forM_ [0..255] $ \i -> do
        when (condition i) $ do
            idx <- get
            lift $ MV.write a' i idx
            put $ idx + 1
    return a'

I simplified it a bit so that each element is set to 0 from the start, we begin with an initial state of idx = 1, loop over [0..255], if the current index i meets the condition then get the current idx, write it to the current index, then increment idx. Run this as a stateful operation, then freeze the vector, and finally run the ST monad side of things. This allows for an actual mutable vector hidden safely within the ST monad so that the outside world doesn't know that to calculate a you have to do some rather strange things.

Answer 3

Explicit recursion:

a = go 0 1
  where go 256 _   = []
        go i   idx | someCondition i = idx : go (i+1) (idx+1)
                   | otherwise       = 0   : go (i+1) idx

Unfolding: (variant of the explicit recursion above)

a = unfoldr f (0,1)
    where f (256,_) = Nothing
          f (i,idx) | someCondition i = Just (idx,(i+1,idx+1))
                    | otherwise       = Just (0  ,(i+1,idx  ))

Answer 4

Loops can usually be expressed using different fold functions. Here is a solution which uses foldl(you can switch to foldl' if you run into a stackoverflow error):

f :: (Num a) => (b -> Bool) -> a -> [b] -> [a]
f pred startVal = reverse . fst . foldl step ([], startVal)
    where            
        step (xs, curVal) x 
            | pred x = (curVal:xs, curVal + 1)
            | otherwise = (0:xs, curVal)

How to use it? This function takes a predicate (someCondition in your code), the initial value of an index and a list of element to iterate over. That is, you can call f someCondition 1 [0..255] to obtain the result for the example from your question.