13

我已经习惯了 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)

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

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

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

最好的选择是什么？

4

2 回答 2

8

我很可能会使用以下内容：

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

一般来说，折叠是惯用的，应该在适合递归模式时使用。否则使用显式递归或尝试重用现有的组合器。如果有一个新的模式，做一个组合器，但前提是你会经常使用这个模式 - 否则它是矫枉过正的。在这种情况下，模式是 fold 对于由定义的非空列表：data List a = End a | Cons a (List a)。

于 2010-08-01T02:41:55.420 回答
4

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

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

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

  3. 我认为这很有意义。正如您所观察到的，这是一个合理认可的“模式”，但我认为它与算法的描述非常匹配，以这种方式写下来。它可能不具有普遍性或可重用性，但鉴于它本质上是算法方法的关键，我认为直接编写案例是有意义的，就像你在 f 之类的函数中所做的那样。这将是我最喜欢的方法。

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

于 2010-08-01T01:25:35.170 回答