将递归守卫更改为更高阶的函数

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]

基于基本的递归，我想知道是否可能有一种方法将此（和类似的函数）转换为更高阶的map，filter或foldr。我不是很先进，这些功能对我来说都是新的。

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

现在，基本案例必须处理空列表，在这种情况下，我们必须返回一个返回空列表的函数，无论boolean参数是什么。因此，我们到达

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

现在，我们需要定义go。这需要作为参数：

1. 列表元素y
2. “递归”的结果qazxsw poi（列表其余部分的函数qazxsw poi）

并且必须为更大的列表返回函数ys。所以我们也要考虑一下

3. 一个布尔参数

最后让Bool->[a]返回一个列表。好吧，如果布尔值是Bool->[a]，我们必须保持列表不变，所以

go

请注意，False的意思是“尾部不变”，所以我们真的重建整个列表不变。

如果boolean为true，我们在go y ys False = y : ys False 中查询谓词。如果这是假的，我们丢弃ys False，并返回列表尾部不变

p y

如果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

，但这种方法并没有概括为更复杂的情况。

所以，就是这样。这种技术很不错，但我并不建议用其他人理解的实际代码。

Answer 2

首先，让我们翻转你的函数的参数顺序。这将使步骤更容易，我们可以在完成后将其翻转。 （我将称之为翻版([a], [a])。）

Bool -> [a]

请注意filterFirst'适用于所有

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

。让我们替换到位：

filterFirst' ys (const True) = ys

使用if-else而不是后卫：

ys

将第二个参数移动到lambda：

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

现在这是我们可以变成

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

的东西。我们要采用的模式是

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与州Monad一起使用时：

filter

Answer 3

这里有一个适合的高阶函数，但它不在基础库中。 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

包的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

Answer 4

Joseph和chi的答案已经展示了如何推导出

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

是长度保留的，foldr不是，所以简单的map必须不适合实施filterFirst。

map（实际上是filterFirst）是无记忆的 - 无论其他元素的结果如何，相同的谓词/函数都应用于列表的每个元素。在filter中，一旦我们看到第一个不满意的元素并将其删除，行为就会改变，所以map（和filterFirst）是不合适的。

filter用于将结构减少为汇总值。这是非常笼统的，如果没有经验，这可能不会立即显而易见。不过，map实际上就是这样的行动。直觉就像是，“我们可以在一次通过结构的过程中构建它，在我们去的时候构建它（根据需要存储额外的状态）吗？”。我担心约瑟夫的回答会有点混淆，因为foldr有4个参数，可能不会立即明显发生了什么，所以让我们尝试一下。

filterFirst

这是第一次尝试。这里的“额外状态”显然是bool，指示我们是否已经删除了一个元素，并且该列表累积在元组的第二个元素中。最后我们打电话给foldr来获取列表。然而，这个实现有一个问题，即我们删除不满足谓词的最右边的元素，因为filterFirst p xs = snd $ foldr (\a (deleted,acc) -> if not deleted && not (p a) then (True,acc) else (deleted,a:acc) ) (False,[]) xs 首先将最右边的元素与中性元素组合，然后是最右边的元素，依此类推。

snd

在这里，我们尝试使用foldr。这确实删除了最左边的非满意元素，但具有反转列表的副作用。我们可以在前面贴上一个filterFirst p xs = snd $ foldl (\(deleted,acc) a -> if not deleted && not (p a) then (True,acc) else (deleted,a:acc) ) (False,[]) xs ，这样可以解决问题，但由于双遍，有点不能令人满意。

然后，如果你回到foldl，已经意识到（基本上）如果你想要变换列表同时保留reverse是正确变体的顺序，你可以玩它一段时间并最终写出约瑟夫建议的内容。然而，我同意chi，直截了当的递归是最好的解决方案。

Answer 5

您的函数也可以表示为展开，或者更具体地说，表示为同态。在解决方案本身之前，请允许我从简短的解释性说明开始。

---

同态是与paramorphism双重的递归方案（有关后者的更多信息，请参阅foldr）。同态是展开的例子，其从种子产生结构。例如，foldr提供dfeuer's answer，列表展开。

Data.List

给unfoldr的函数接受一个种子并产生一个列表元素和一个新种子（如果可能值是一个unfoldr :: (b -> Maybe (a, b)) -> b -> [a] ）或终止列表生成（如果它是unfoldr）。展开通常由递归方案的Just函数表示（“ana”是“anamorphism”的缩写）。

Nothing

专门列表，这变成......

ana

......这是不同服装的ana :: Corecursive t => (a -> Base t a) -> a -> t 。

同态是一种展开，其中结构的产生可以在过程的任何点被短路，通过一次性地产生结构的其余部分而不是新的种子。在列表的情况下，我们有：

ana @[_] :: (b -> ListF a b) -> b -> [a]

unfoldr用于触发短路：使用apo @[_] :: (b -> ListF a (Either [a] b)) -> b -> [a] 结果，展开短路，而使用Either则正常进行。

---

Left方面的解决方案相当直接：

Right

它比dfeuer的基于apo的解决方案更加尴尬，因为如果我们想要在没有空列表的情况下进行短路，我们就会被迫发出一个额外的元素（短路情况下的

{-# LANGUAGE LambdaCase #-}

import Data.Functor.Foldable

filterFirst :: (a -> Bool) -> [a] -> [a]
filterFirst p = apo go
  where
  go = \case
    [] -> Nil
    a : as
      | p a -> Cons a (Right as) 
      | otherwise -> case as of
        [] -> Nil
        b : bs -> Cons b (Left bs) 

），所以我们有看看前面的一个位置。这种尴尬会增加几个数量级，如果，而不是para，我们是在展开普通的老b展开，如filterFirst精美的解释。

Answer 6

这个答案的灵感来自filter关于一个现已删除的问题。

List filter using an anamorphism可以用a comment from luqui相当直接的方式实现：

filterFirst

span在第一个不符合条件的元素中将列表拆分为两个。在

filterFirst :: (a -> Bool) -> [a] -> [a]
filterFirst p = (\(yeas, rest) -> yeas ++ drop 1 rest) . span p

之后，我们删除列表第二部分的第一个元素（使用span :: (a -> Bool) -> [a] -> ([a], [a])而不是span，这样我们就不必为drop 1添加特殊情况），并使用tail重新组合列表。

顺便说一句，这个实现有一个几乎无点的拼写，我发现太漂亮了，更不用说了：

[]

---

虽然(++)是一个更高阶函数，但如果您在问题的上下文中发现此实现令人失望，则完全可以理解。毕竟，

filterFirst :: (a -> Bool) -> [a] -> [a]
filterFirst p = uncurry (++) . second (drop 1) . span p

并不比span本身更基本。难道我们不应该尝试更深入一点，看看我们是否可以在将其表达为折叠或其他递归方案时捕捉此解决方案的精神？

我相信像span这样的函数可以很好地证明了hylomorphisms。一个hylomorphism是一个展开（参见filterFirst的更多内容），它生成一个中间数据结构，然后是一个折叠，将这个数据结构变成其他东西。虽然它可能看起来需要两次传递来获得结果（一个通过输入结构，另一个通过中间结果），如果hylomorphism正确实现（如在递归方案的filterFirst函数中所做的那样），它可以完成在一次通过中，折叠消耗中间结构的碎片，因为它们是由展开产生的（因此我们不必实际构建它只是为了将其撕下）。

在开始之前，这是运行以下内容所需的样板：

my other answer

这里的策略是为hylomorphism选择一个中间数据结构，表达我们想要实现的目标的本质。在这种情况下，我们将使用这个可爱的东西：

hylo

{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TemplateHaskell #-}

import Data.Functor.Foldable
import Data.Functor.Foldable.TH

非常像一个列表（

data BrokenList a = Broken [a] | Unbroken a (BrokenList a)
    -- I won't actually use those instances here,
    -- but they are nice to have if you want to play with the type.
    deriving (Eq, Show, Functor, Foldable, Traversable)
makeBaseFunctor ''BrokenList 

和BrokenList镜像Broken和Unbroken，而[]咒语生成类似于(:)的makeBaseFunctor基础函子，与BrokenListF和ListF构造函数），除了它的末尾附加了另一个列表（BrokenF构造函数） ）。它以一种非常直接的方式表达了将列表分为两部分的想法。

随着UnbrokenF在手，我们可以写出hylomorphism。 Broken是用于展开的操作，BrokenList是用于折叠的那个。

coalgSpan

algWeld在击中

filterFirst p = hylo algWeld coalgSpan
    where
    coalgSpan = \case
        [] -> BrokenF []
        x : xs
            | p x -> UnbrokenF x xs
            | otherwise -> BrokenF xs
    algWeld = \case
        UnbrokenF x yeas -> x : yeas
        BrokenF rest -> rest

元素时打破了名单，使coalgSpan不成立。不将该元素添加到列表的第二部分（x而不是p x）负责过滤。至于BrokenF xs，它用于连接这两个部分（它非常类似于我们用BrokenF (x : xs)实现algWeld）。

（有关(++)的类似示例，请参阅cata注释5中的BrokenList实现。它建议使用此策略实现breakOn需要什么。）

这个基于this older answer of mine的实现至少有两个好处。首先，它具有良好的性能（临时测试表明，如果使用优化编译，它至少与其他答案中最有效的实现一样好，并且可能稍快一些）。其次，它非常接近地反映了你对span的原始的，显式的递归实现（或者，无论如何，比仅折叠和展开的实现更接近）。