将递归保护转换为高阶函数

Question

我正在尝试将基本函数转换为高阶函数(特别是map、filter或foldr)。我想知道是否有任何简单的概念可以应用到我可以看到我用警卫编写的旧函数的地方，并将它们转换为更高的级别。

我正在修改一个名为filterFirst的函数，它从不满足给定谓词函数(第一个参数)的列表(第二个参数)中删除第一个元素。

filterFirst :: (a -> Bool) -> [a] -> [a]
filterFirst _ [] = []
filterFirst x (y:ys)
    | x y       = y : filterFirst x ys
    | otherwise = ys

举个例子：

 greaterOne :: Num a=>Ord a=>a->Bool
 greaterOne x = x > 1

 filterFirst greaterOne [5,-6,-7,9,10]
 [5,-7,9,10]

基于基本的递归，我想知道是否有一种方法可以将这个(和类似的函数)转换成更高阶的映射、过滤器或文件夹。我不是很先进，这些功能对我来说都是新的。

Answer 1

如果我们真的需要的话，我们可以使用filterFirst编写foldr，因为foldr是某种“通用的”--它允许我们可以使用递归执行的任何列表转换。主要的缺点是，产生的代码是相当违反直觉的。在我看来，在这种情况下显式递归要好得多。

不管怎么说，这是怎么做的。这依赖于我认为是反模式的东西，即“向foldr传递四个参数”。我称这为反模式，因为foldr通常只使用三个参数调用，并且结果不是一个带有第四个参数的函数。

filterFirst :: (a->Bool)->[a]->[a]
filterFirst p xs = foldr go (\_ -> []) xs True
   where
   go y ys True 
      | p y = y : ys True 
      | otherwise = ys False
   go y ys False = y : ys False

明白了吗？不是很好。这里的诀窍是利用foldr构建一个函数Bool -> [a]，如果用False调用，它返回原始列表，如果用True调用，则返回过滤后的第一个列表。如果我们使用

foldr go baseCase xs

结果很明显

foldr go baseCase xs True

现在，基本大小写必须处理空列表，在这种情况下，无论布尔参数是什么，我们都必须返回返回空列表的函数。因此，我们到达

foldr go (\_ -> []) xs True

现在，我们需要定义go。这是一种论点：

1. 列表元素y
2. “递归”ys (列表其余部分的函数Bool->[a] )的结果。

必须为更大的列表返回一个函数Bool->[a]。所以我们也要考虑

1. 布尔参数

最后使go返回一个列表。如果布尔值是False，我们必须返回不变的列表，所以

go y ys False = y : ys False

请注意，ys False的意思是“尾不变”，因此我们实际上是在重新构建整个列表，没有改动。

如果布尔值为true，则查询谓词(如p y中的谓词)。如果为false，则放弃y，并将列表尾不变地返回

   go y ys True 
      | p y = -- TODO
      | otherwise = ys False

如果p y为真，则保留y，并返回筛选后的列表尾。

   go y ys True 
      | p y = y : ys True
      | otherwise = ys False

最后，我们使用了一对([a], [a])而不是函数Bool -> [a]，但是这种方法并没有推广到更复杂的情况。

所以仅此而已。这种技术是很好的了解，但我不推荐它在真正的代码，这是为了让其他人理解。

Answer 2

这里有一个高阶函数是合适的，但它不在基库中。foldr有什么问题？如果您只是折叠列表，您将最终重建整个事情，包括删除后的部分。

作业的一个更合适的函数是来自para包的recursion-schemes (我已经重命名了一个类型变量)：

para :: Recursive t => (Base t (t, r) -> r) -> t -> r

在列表的情况下，这专门用于

para :: (ListF a ([a], r) -> r) -> [a] -> r

哪里

data ListF a b = Nil | Cons a b
  deriving (Functor, ....)

这与foldr非常相似。recursion-schemes等价于foldr是

cata :: Recursive t => (Base t r -> r) -> t -> r

专门为

cata :: (ListF a r -> r) -> [a] -> r

在这里休息一下，找出为什么cata的类型与foldr的类型基本相同。

cata和para的不同之处在于，para传递的折叠函数不仅是折叠的结果超过列表的尾部，而且是列表本身的尾部。在找到第一个不匹配元素之后，这为我们提供了一种简单高效的方法来生成列表的其余部分：

filterFirst :: (a -> Bool) -> [a] -> [a]
filterFirst f = para go
  where
    --go :: ListF a ([a], [a]) -> [a]
    go (Cons a (tl, r))
      | f a = a : r
      | otherwise = tl
    go Nil = []

para对于列表来说有点尴尬，因为它被设计成适合于更一般的上下文。但是，正如cata和foldr基本上是等价的，我们可以为列表编写一个稍微不那么尴尬的函数。

foldrWithTails
  :: (a -> [a] -> b -> b)
  -> b -> [a] -> b
foldrWithTails f n = go
  where
    go (a : as) = f a as (go as)
    go [] = n

然后

filterFirst :: (a -> Bool) -> [a] -> [a]
filterFirst f = foldrWithTails go []
  where
    go a tl r
      | f a = a : r
      | otherwise = tl

Answer 3

首先，让我们翻转一下函数的参数顺序。这将使一些步骤更简单，我们可以在完成后将其倒转。(我会打电话给翻转版filterFirst'。)

filterFirst' :: [a] -> (a -> Bool) -> [a]
filterFirst' [] _ = []
filterFirst' (y:ys) x
    | x y       = y : filterFirst' ys x
    | otherwise = ys

请注意，filterFirst' ys (const True) = ys适用于所有ys。让我们替换一下这一点：

filterFirst' :: [a] -> (a -> Bool) -> [a]
filterFirst' [] _ = []
filterFirst' (y:ys) x
    | x y       = y : filterFirst' ys x
    | otherwise = filterFirst' ys (const True)

使用if-否则而不是警卫：

filterFirst' :: [a] -> (a -> Bool) -> [a]
filterFirst' [] _ = []
filterFirst' (y:ys) x = if x y then y : filterFirst' ys x else filterFirst' ys (const True)

将第二个参数移到lambda：

filterFirst' :: [a] -> (a -> Bool) -> [a]
filterFirst' [] = \_ -> []
filterFirst' (y:ys) = \x -> if x y then y : filterFirst' ys x else filterFirst' ys (const True)

现在我们可以把它变成一个foldr了。我们所追求的模式是，filterFirst' (y:ys)可以用filterFirst' ys来表示，而不必使用ys，我们现在就在那里了。

filterFirst' :: Foldable t => t a -> (a -> Bool) -> [a]
filterFirst' = foldr (\y f -> \x -> if x y then y : f x else f (const True)) (\_ -> [])

现在我们只需要稍微整理一下：

filterFirst' :: Foldable t => t a -> (a -> Bool) -> [a]
filterFirst' = foldr go (const [])
  where go y f x
          | x y       = y : f x
          | otherwise = f (const True)

然后把论点倒过来：

filterFirst :: Foldable t => (a -> Bool) -> t a -> [a]
filterFirst = flip $ foldr go (const [])
  where go y f x
          | x y       = y : f x
          | otherwise = f (const True)

我们就完蛋了。filterFirst是用foldr实现的。

增编:虽然filter还不够强大，但当与State一起使用时，filterM是这样的：

{-# LANGUAGE FlexibleContexts #-}

import Control.Monad.State

filterFirst :: (a -> Bool) -> [a] -> [a]
filterFirst x ys = evalState (filterM go ys) False
  where go y = do
          alreadyDropped <- get
          if alreadyDropped || x y then
            return True
          else do
            put True
            return False