On control flow structures in Haskell (multiple if-then-else)

Question

I want to translate the following procedural program to Haskell [written in pseudocode]:

f(x) {
  if(c1(x)) {
     if(c2(x)) {
        return a(x);
     }
     else if (c3(x)) {
      if(c4(x)) {
         return b(x);
     }
  }
  return d(x);
}

I have written the following implementation:

f x = 
  if (c1 x) then
     if(c2 x) then 
            a x
     else if (c3 x) then
              if (c4 x) then
                  b x
              else d x
     else d x
  else d x 

Unfortunately it contains (else d x) three times.

Is there a better way to implement the function? (i.e, to return (d x) if none of the conditions was met?)

I understand that we could combine conditions c1 and c2 into (c1 x) && (c2 x) to make the number of if's smaller, but my conditions c1, c2, c3, c4 are indeed very long and if I combine them I will get a condition which takes more than one line.

Answer 1

Easiest, most apparent solution

If you're using GHC, you can turn on

{-# LANGUAGE MultiWayIf #-}

and your entire thing becomes

f x = if | c1 x && c2 x         -> a x
         | c1 x && c3 x && c4 x -> b x
         | otherwise            -> d x

---

Slightly more advanced and flexible solution

However, it's not always you want to blindly replicate imperative code in Haskell. Often, it's useful to think of your code as data instead. What you are really doing is setting up a list of requirements that x must satisfy, and then if x satisfies those requirements you take some action on x.

We can represent this with actual lists of functions in Haskell. It would look something like

decisions :: [([a -> Bool], a -> b)]

decisions = [([c1, c2],     a)
            ,([c1, c3, c4], b)]
            ,([],           d)]

Here, we should read this as, "if x satisfies both c1 and c2, take action a on x" and so on. Then we can define f as

f x = let maybeMatch = find (all ($ x) . fst) decisions
          match = fromMaybe (error "no match!") maybeMatch
          result = snd match
      in  result x

This works by walking through the list of requirements and finding the first set of decisions that x satisfy (maybeMatch). It pulls that out of the Maybe (you might want some better error handling there!) Then it chooses the corresponding function (result), and then it runs x through that.

---

Very advanced and flexible solution

If you have a really complex tree of decisions, you might not want to represent it with a flat list. This is where actual data trees come in handy. You can create a tree of the functions you want, and then search that tree until you hit a leaf node. That tree might in this example look something like

+-> c1 +-> c2 -> a
|      |
|      +-> c3 -> c4 -> b
+-> d

In other words, if x satisfies c1, it's gonna see if it satisfies c2 too, and if it does take action a on x. If it doesn't, it goes on to the next branch with c3, and so on, until it reaches an action (or has walked through the entire tree).

But first you're going to need a data type to tell the difference between a requirement (c1, c2 etc.) and an action (a, b etc.)

data Decision a b = Requirement (a -> Bool)
                  | Action (a -> b)

Then you build a tree of decisions as

decisions =
  Node (Requirement (const True))
    [Node (Requirement c1)
       [Node (Requirement c2)
          [Node (Action a) []]
       ,Node (Requirement c3)
          [Node (Requirement c4)
             [Node (Action b) []]]
    ,Node (Action d) []]

This looks more complicated than it is, so you should probably invent a neater way of expressing decision trees. If you define the functions

iff = Node . Requirement
action = flip Node [] . Action

you can write the tree as

decisions =
  iff (const True) [
      iff (c1) [
          iff (c2) [
              action a
          ],
          iff (c3) [
              iff (c4) [
                  action b
              ]
          ]
      ],
      action d
  ]

and suddenly it's very similar to the imperative code you started with, despite the fact that it's valid Haskell code that's just building a data structure! Haskell is powerful for defining custom little "languages inside the language" like this.

Then you need to search through the tree for the first action you can reach.

decide :: a -> Tree (Decision a b) -> Maybe b

decide x (Node (Action f) _) = Just (f x)
decide x (Node (Requirement p) subtree)
  | p x       = asum $ map (decide x) subtree
  | otherwise = Nothing

This uses a little bit of Maybe magic (asum) to stop at the first successful hit. This in turn means it will not compute the conditions of any branch in vain (which is efficient and important if the computations are expensive) and it should handle infinite decision trees just fine.

You can make decide even more general, taking full advantage of the Alternative class, but I've chosen to specialise it for Maybe so as to not write a book about this. Making it even more general might allow you to have fancy monadic decisions too, which would be very cool!

But, lastly, as a very simple example of this in action – take the Collatz conjecture. If you give me a number, and ask me what the next number should be, I can build a decision tree to find out. The tree may look like this:

collatz =
  iff (> 0) [
      iff (not . even) [
          action (\n -> 3*n + 1)
      ],
      action (`div` 2)
  ]

so the number has to be bigger than 0, and then if it's odd you multiply by three and add one, otherwise you halve it. Test runs show that

λ> decide 3 collatz
Just 10
λ> decide 10 collatz
Just 5
λ> decide (-4) collatz
Nothing

You can probably imagine much more interesting decision trees.

---

Edit like a year later: The generalisation to Alternative is actually very simple, and fairly interesting. The decide function gets the new look

decide :: Alternative f => a -> Tree (Decision a b) -> f b

decide x (Node (Action f) _) = pure (f x)
decide x (Node (Requirement p) subtree)
  | p x       = asum $ map (decide x) subtree
  | otherwise = empty

(that's a total of only three changes, for those keeping count.) What this gives you is the opportunity to assemble "all" actions the input satisfies by using the applicative instance of lists instead of Maybe. This reveals an "error" in our collatz tree – if we look carefully at it, we see it says that all odd and positive integers n turn to 3*n +1 but it also says that all positive numbers turn to n/2. There is no additional requirement that says the number has to be even.

In other words, the (`div` 2) action is only under the (>0) requirement and nothing else. This is technically incorrect, but it happens to work if we just get the first result (which is basically what using the Maybe Alternative instance does). If we list all results, we also get an incorrect one.

When is getting multiple results interesting? Maybe we're writing the decision tree for an AI, and we want to humanise the behaviour by first getting all the valid decisions, and then picking one of them at random. Or ranking them based on how good they are in the circumstances, or something else.