19

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.

1
  • This belongs on codereview.stackexchange
    – Dexygen
    May 7, 2014 at 14:26

4 Answers 4

39

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.

3
  • Thank you! That's definitely more than I expected to learn from the question. May 7, 2014 at 2:54
  • 5
    A more portable, if slightly hacky, version of the easiest solution: use a case statement and guards. To wit: case () of _ | c1 x && c2 x -> a x ; | c1 x && c3 x && c4 x -> b x ; | otherwise -> d x. I'd prefer MultiWayIf when using a recent enough GHC, though; but on older versions, you can't, and this is how it was emulated. May 7, 2014 at 2:59
  • 1
    @AntalS-Z Absolutely! Other answers had already covered that though, so I decided to not add it to my answer as well, to keep it short. My hopes is that when future Google people arrive, MultiWayIf isn't too new. The GHC documentation states the equivalence as well, for anyone further interested.
    – kqr
    May 7, 2014 at 8:17
19

You could use guards and a where clause:

f x | cb && c2 x = a x
    | cb && c3 x && c4 x = b x
    | otherwise = d x
  where cb = c1 x
1
  • 1
    Exactly how I would have done it; short, structured and easy to read May 7, 2014 at 7:49
16

If you're just worried about writing them out then that's what where blocks are for

f x = 
  case () of
    () | c1 && c2       -> a x
       | c1 && c3 && c4 -> b x
       | otherwise      -> d x
  where
    c1 = ...
    c2 = ...
    c3 = ...
    c4 = ...

Not that I'm using the case trick to introduce a new place for guard statements. I can't use guards on the function definition itself because the where clause won't scope over all of the guards. You could use if just the same, but guards have nice pass-through semantics.

2
  • Shouldn't that be Note that I'm using... ? May 7, 2014 at 6:21
  • 3
    where clauses do scope over multiple guards. It's only multiple argument patterns they don't scope over. May 7, 2014 at 11:04
8

There's another pattern you can use: I wouldn't use it in your specific example but there are very similar situations where I have used it.

f x = case (c1 x, c2 x, c3 x, c4 x) of
  (True,True,_,_) -> a x
  (True,False,True,True) -> b x
  _ -> d x

Only the bare minimum evaluation required to choose which path to take will actually be evaluated: it won't actually evaluate c2 x unless c1 x is True.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.