常见的递归模式

Question

我正在习惯 Haskell 的高阶函数。通常我可以用诸如映射、折叠和扫描之类的函数来替换显式的递归模式。然而，我经常遇到以下递归模式，我不明白如何使用高阶函数来表达：

   f (x:[]) = k x
   f (x:xs) = g x (f xs)

例如，假设我正在表示分析画面。然后我创建一个数据类型，例如：

   data Tableau = N Expr | S Expr (Tableau) | B Expr (Tableau) (Tableau)

如果我想将 Expr 列表转换为表格结构，我想要一个函数部分，其可能类似于：

   f (x:[]) = N x
   f (x:xs) = S x (f xs)

现在，我看到三个选项： (1 ）创建一个函数，在给定一个表格和一个列表的情况下，该函数决定表格中的下一个分支应该是 S 还是 N （或 B >，但我们会忽略这种情况）； (2) 使用高阶函数封装f的递归模式； (3) 使用像f这样的函数。

最好的选择是什么？

Answer 1

我最有可能使用以下内容：

f xs = foldr g (k (last xs)) (init xs)

它基本上意味着折叠时列表的末尾被 k x 替换。由于惰性求值随处可见，它甚至适用于无限列表。

还有另外两种解决方案 - 添加空案例和使用 Maybe。

A) 添加空大小写：

如果 f [] 定义良好，那就最好了。然后，您可以将定义编写为

f [] = c
f (x:xs) = g x (f xs)

f =foldr g c。例如，如果更改

data Tableau = N Expr | S Expr Tableau | B Expr Tableau Tableau

为

data Tableau = N | S Expr Tableau | B Expr Tableau Tableau

then 则可以将单元素 tableaux 表示为 S expr N，并且该函数被定义为单行函数

f = foldr S N

只要空情况有意义，这就是最佳解决方案。

B) 使用 Maybe：

另一方面，如果 f [] 不能被合理地定义，情况会更糟。
偏函数通常被认为是丑陋的。为了使其完整，您可以使用也许。 Define

 f [] = Nothing
 f [x] = Just (k x)
 f (x:xs) = Just (g x w)
            where Just w = f xs

It 是一个完整的函数——这样更好。

但现在您可以将函数重写为：

 f [] = Nothing
 f (x:xs) = case f xs of
              Nothing -> Just (k x)
              Just w -> Just (g x w)

这是正确的折叠：

 addElement :: Expr -> Maybe Tableaux -> Maybe Tableaux
 addElement x Nothing = Just (N x)
 addElement x (Just w) = Just (S x w)

 f = foldr addElement Nothing

一般来说，折叠是惯用的，应该在适合递归模式时使用。否则使用显式递归或尝试重用现有的组合器。如果有新模式，请创建一个组合器，但前提是您会经常使用该模式 - 否则就太过分了。在这种情况下，对于非空列表，该模式是折叠的，定义如下：data List a = End a |缺点（列表a）。

Answer 2

如果我正确理解了这个问题，那么这是我对您的选项的评估：

1. 为了编写该函数，必须从构造函数下面匹配（可能是任意复杂的？）表格，这可能有点令人讨厌。这种方法看起来有点脆弱，尽管它可能工作得很好。

2. 我认为没有必要概括该模式，因为它是在递归结构上运行的递归函数。引入高阶模式（我认为）会混淆执行此数据结构的递归遍历背后的实际逻辑。

3. 我认为这很有道理。正如您所观察到的，这是一个合理认可的“模式”，但我认为它与算法的描述很好地匹配，以这种方式将其写下来。它可能不那么通用或可重用，但考虑到它本质上是算法方法的关键，我认为像在 f 这样的函数中所做的那样直接编写案例是有意义的。这将是我最喜欢的方法。

很抱歉没有提供特别具体的答案，但这是一个相当主观的答案，因此考虑到上述三个选项，出于清晰性和可读性的原因，我会选择选项 3。