Is there a difference in Haskell, regarding tail-recursion, between using guards that return boolean values and using (||) operators?

Question

Let's use the following function as an example:

findWord :: [[Char]] -> [(Int, Int)] -> (Int, Int) -> String -> Bool
findWord _ _ _ [] = True                         -- Word was found
findWord xs ys (row, col) (z : zs)
  | (<) row 0  = False                           -- Index out of Bounds
  | (<) col 0 = False                            -- Index out of Bounds
  | (>=) row (length xs) = False                 -- Index out of Bounds
  | (>=) col (length $ head xs) = False          -- Index out of Bounds
  | (/=) z $ xs !! row !! col = False            -- Letter doesn't match
  | (row, col) `elem` ys = False                 -- Coords already visited
  | findWord xs visited (row - 1, col) zs = True -- Check Top
  | findWord xs visited (row + 1, col) zs = True -- Check Bottom
  | findWord xs visited (row, col - 1) zs = True -- Check Left
  | findWord xs visited (row, col + 1) zs = True -- Check Right
  | otherwise = False
  where
    visited = (row, col) : ys                    -- Add to visited list 

In it, the final three guards could be replaced by (||), the middle three = True and the | otherwise = False deleted to give us the same exact result, with the upside of being slightly less verbose. I assume, however, that my code wouldn't be tail-recursive if I did so, even though (||) is lazily-evaluated in Haskell.

Is my assumption correct, or is GHC smart enough to optimize it?

Answer 1

@amalloy's answer is good, but I think they might have misunderstood part of your question. I think you were asking about the difference between:

| findWord xs visited (row - 1, col) zs = True
| findWord xs visited (row + 1, col) zs = True
| findWord xs visited (row, col - 1) zs = True
| findWord xs visited (row, col + 1) zs = True

and

| findWord xs visited (row - 1, col) zs
  || findWord xs visited (row + 1, col) zs
  || findWord xs visited (row, col - 1) zs
  || findWord xs visited (row, col + 1) zs = True

If so, there is no difference in the generated optimized code.

As @amalloy says, neither is tail recursive, so that's not an issue. Don't be fooled by superficial syntax. Tail recursion means that the current function context is abandoned in favor of the recursive call; that can't happen here because -- in both cases -- if the first recursive call returns False, the current function context must be preserved to make the additional recursive calls. (Even the last call can't be made tail recursive, because a False result needs to be turned into a pattern match error, since your cases are non-exhaustive.)

Anyway, the first, guards-only version is immediately desugared into the equivalent of:

case findWord xs visited (row - 1, col) zs of
  False -> case findWord xs visited (row + 1, col) zs of
    False -> case findWord xs visited (row, col - 1) zs of
      False -> case findWord xs visited (row, col + 1) zs of
        False -> ...non-exhaustive pattern error...
        True -> True
      True -> True
    True -> True
  True -> True

The second, boolean version is desugared into:

case findWord xs visited (row - 1, col) zs
  || findWord xs visited (row + 1, col) zs
  || findWord xs visited (row, col - 1) zs
  || findWord xs visited (row, col + 1) zs of
    False -> ...non-exhaustive pattern error...
    True -> True

but since the definition of || itself desugars into:

x || y = case x of
           False -> y
           True -> True

inlining of the (right associative) || calls will give:

-- outer case
case (
      -- inline of first (||)
      case findWord xs visited (row - 1, col) zs of
        False ->
          -- inline of second (||)
          case findWord xs visited (row + 1, col) zs of
            False ->
              -- inline of third (||)
              case findWord xs visited (row, col - 1) zs of
                False -> 
                  findWord xs visited (row, col + 1) zs
                True -> True
            True -> True
        True -> True) of
  False -> ...non-exhaustive pattern error...
  True -> True

and a so-called "case-of-case" optimization will apply the outer case to each of the results generated by the inner case, which "converts" all the True results to True, and wraps an extra case around the innermost findWord call:

case findWord xs visited (row - 1, col) zs of
  False ->
    case findWord xs visited (row + 1, col) zs of
      False ->
        case findWord xs visited (row, col - 1) zs of
          False -> 
            -- NOTE: the outer case has been applied here
            case findWord xs visited (row, col + 1) zs of
              False -> ...non-exhaustive pattern error...
              True -> True
          True -> True  -- NOTE: outer case has also been applied
      True -> True      -- to all these "True" results, which left
  True -> True          -- them unchanged.

This is equivalent to the guards-only version. So, in any normal situation compiling with optimizations -O, the two versions will quickly converge to the same intermediate compiler representation, and will result in equivalent final code.

(In this case, if you stick both versions of the function in a file and compile with ghc -O -fforce-recomp -ddump-simpl -dsuppress-all -dsuppress-uniques, you can see the optimized "core" representations, and a careful side by side comparison will show them to be equivalent. In smaller examples, GHC will actually calculate that the two are equivalent and define one of them as equal to the other in this core output.)

So, your choice between these alternatives should be based on readability of the code. On that front, I don't think there is a clear winner that applies in all situations. If I was doing a full code review, I would probably have several suggestions, and "rewrite your guards as boolean expressions" wouldn't make the list.