haskell - 常见的递归模式

Question

我已经习惯了 Haskell 的高阶函数。通常我可以用 map、fold 和 scan 等函数替换显式递归模式。但是，我经常遇到以下递归模式，我不明白如何使用高阶函数来表达:

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

例如，假设我代表分析画面。然后我创建一个数据类型，例如:

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

如果我想转换 Expr 的列表s 到一个表格结构中，我想要一个可能类似于的函数部分:

   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

那么您可以将单元素画面表示为 S expr N , 函数定义为单行

f = foldr S N

只要空壳有意义，这是最好的解决方案。

B)使用也许:

另一方面，如果 f []无法合理定义，情况更糟。
偏函数通常被认为是丑陋的。总而言之，您可以使用 Maybe .定义

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

这是一个完整的功能 - 更好。

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

 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 | Cons a (List a) .