Haskell中守卫表达式与(||)运算符的尾递归差异及GHC优化问题

先看原findWord函数代码：

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 

问题 #

这个函数的最后四个守卫可以用||运算符替换，移除中间三个= True和最后的| otherwise = False，得到更简洁的版本。但我假设替换后的代码不再是尾递归——尽管Haskell的||是惰性求值的。请问这个假设是否正确，还是GHC足够智能能对其做优化？

回答 #

你的假设从严格定义来说是对的，但GHC的优化能力可以让替换后的代码和原尾递归版本的执行效率几乎一致，不会有栈溢出之类的问题，具体分析如下：

1. 尾递归的严格定义
   尾递归要求递归调用是函数的最后一个操作，调用后不需要再执行其他计算。替换后的代码用||串联四个递归调用，比如：

| otherwise = 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

这里第一个递归调用返回后，还要执行||的后续判断，所以严格来说不算尾递归。

2. GHC的短路求值优化
   Haskell的||是惰性求值的——只要前面的表达式返回True，后面的表达式就不会被计算。GHC的优化器（尤其是开启-O2级别优化时）会把这种链式的短路调用转换成类似尾递归的跳转结构：一旦某个递归分支返回True，就直接返回结果，不会保留之前的栈帧；只有当前面的分支都返回False时，才会继续执行下一个递归调用，这和原代码守卫分支的执行逻辑完全一致。

3. 两种写法的实际表现
   原代码的守卫分支本质上就是手动实现的短路判断，和用||的写法逻辑等价。GHC对这两种写法的优化结果几乎没有差异，都不会因为递归深度导致栈溢出问题。

所以不用太担心替换后的性能问题，GHC会帮你把这种短路调用优化得和原尾递归版本一样高效。

内容的提问来源于stack exchange，提问作者Sky Sumisu