Haskell：如何缓存函数调用结果优化树搜索实现

首先是你定义的代数数据类型：

data Tree a = Empty | Node a (Tree a) (Tree a)
  deriving (Show, Eq)

data Step = StepL | StepR
  deriving (Show, Eq)

你的原始search实现存在重复调用searchHelper的问题：每次判断左/右子树搜索结果是否有效时，会先执行一次递归调用，确认非空后又重复执行一次完全相同的调用，既浪费计算资源，代码也不够简洁。

方案1：用let绑定缓存递归结果 #

通过let绑定把左子树的搜索结果缓存起来，之后直接复用这个结果即可，无需重复调用：

searchHelper :: Eq a => a -> Tree a -> [Step] -> Maybe [Step]
searchHelper _ Empty _ = Nothing
searchHelper targetValue (Node nodeValue leftChild rightChild) stepsSoFar
  | targetValue == nodeValue = Just stepsSoFar
  | otherwise =
      let leftResult = searchHelper targetValue leftChild (stepsSoFar ++ [StepL])
      in case leftResult of
           Just _ -> leftResult
           Nothing -> searchHelper targetValue rightChild (stepsSoFar ++ [StepR])

search :: Eq a => a -> Tree a -> Maybe [Step]
search targetValue root = searchHelper targetValue root []

方案2：利用Maybe的Alternative特性（更简洁） #

Maybe类型是Alternative类型类的实例，<|>操作符会优先返回左侧的Just值，若左侧为Nothing则返回右侧结果。借助这个特性可以写出更简洁的代码：

searchHelper :: Eq a => a -> Tree a -> [Step] -> Maybe [Step]
searchHelper _ Empty _ = Nothing
searchHelper targetValue (Node nodeValue leftChild rightChild) stepsSoFar
  | targetValue == nodeValue = Just stepsSoFar
  | otherwise = leftResult <|> rightResult
  where
    leftResult = searchHelper targetValue leftChild (stepsSoFar ++ [StepL])
    rightResult = searchHelper targetValue rightChild (stepsSoFar ++ [StepR])

search :: Eq a => a -> Tree a -> Maybe [Step]
search targetValue root = searchHelper targetValue root []

额外优化：提升路径构建效率 #

原代码中用++拼接列表效率较低（因为++需要遍历整个左侧列表），可以改为在列表头部添加步骤，最后找到目标节点时反转路径：

searchHelper :: Eq a => a -> Tree a -> [Step] -> Maybe [Step]
searchHelper _ Empty _ = Nothing
searchHelper targetValue (Node nodeValue leftChild rightChild) stepsSoFar
  | targetValue == nodeValue = Just (reverse stepsSoFar)
  | otherwise = leftResult <|> rightResult
  where
    leftResult = searchHelper targetValue leftChild (StepL : stepsSoFar)
    rightResult = searchHelper targetValue rightChild (StepR : stepsSoFar)

search :: Eq a => a -> Tree a -> Maybe [Step]
search targetValue root = searchHelper targetValue root []

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