常见的递归模式

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)

如果我想将Exprs 列表转换为tableau结构,我想要一个函数部分可能类似于:

   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)使用Maybe:

另一方面,如果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).