我正在尝试将基本函数转换为高阶函数（特别是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。我不是很高级，这些函数对我来说是新的。
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
首先，让我们颠倒函数的参数顺序。这样可能会更加容易一些，等到完成后我们再将其翻转回来。（我将称之为颠倒后的版本filterFirst'。）
filterFirst' :: [a] -> (a -> Bool) -> [a]
filterFirst' [] _ = []
filterFirst' (y:ys) x
| x y = y : filterFirst' ys x
| otherwise = ys
ys，filterFirst' ys (const True) = ys。 让我们将其替换为以下内容：filterFirst' :: [a] -> (a -> Bool) -> [a]
filterFirst' [] _ = []
filterFirst' (y:ys) x
| x y = y : filterFirst' ys x
| otherwise = filterFirst' ys (const True)
使用 if-else 而不是 guard：
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)
我们完成了。利用foldr实现了filterFirst。
补充：虽然filter不足以构建这个函数，但与State Monad一起使用时，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
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
现在，基本情况必须处理空列表，在这种情况下，我们必须返回一个返回空列表的函数，无论布尔参数是什么。因此，我们得到
def filter_list(lst, f):
if not lst:
return lambda _: []
"最初的回答"
foldr go (\_ -> []) xs True
go 函数。它的参数包括：
yys（对于列表的其余部分是一个 Bool->[a] 函数）go 必须返回一个 Bool->[a] 函数来处理更大的列表。所以让我们考虑：
最后，让 go 返回一个列表。如果布尔值为 False，我们必须返回原始列表，因此：
最初的回答：
现在，我们需要定义函数 `go`。它的参数包括：go y ys False = y : ys False
ys False 意味着“尾部未更改”，因此我们实际上是在重建整个列表而没有做任何修改。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]，但这种方法在处理更复杂的情况时不太适用。foldr 是反模式。在某些情况下（不是这种情况），它实际上可以产生清晰的代码。在某些情况下（特别是在编写高性能库代码时），需要利用 GHC 的列表融合优化。而且在将列表消耗函数泛化为 Foldable 消耗函数时，经常需要使用它。 - dfeuerfilterFirst p xs = foldr go id xs xs where go x r ~(_:xs) | p x = x : r xs | otherwise = xs有什么看法？从融合的角度来看，这样做好吗？（元澄清：我在这里并不是要争论；我想了解你的立场）。谢谢。 - Will Nessfoldr的任何优势。 - dfeuerJoseph和chi的答案已经展示了如何推导出foldr的实现，所以我会尝试帮助理解。
map保持长度不变，而filterFirst则不是，因此显然map不适合实现filterFirst。
filter（以及map）是无记忆的 - 相同的谓词/函数应用于列表的每个元素，而不考虑其他元素的结果。在filterFirst中，一旦我们看到第一个不满意的元素并将其删除，行为就会发生变化，因此filter（以及map）不适合。
foldr 用于将结构减少为摘要值。它非常通用，如果没有经验，可能不会立即明确这种操作可以涵盖哪些内容。但是，filterFirst 实际上就是这样的一种操作。直觉上，我们可以像这样思考：“我们能否通过单次遍历结构来构建它，并随着遍历的进行逐步构建它（并根据需要存储额外状态）？”我担心 Joseph 的答案有点含糊不清，因为使用 4 个参数的 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，这样就可以解决问题，但由于双重遍历而有些不令人满意。
然后，如果你回到foldr，意识到如果你想要转换一个列表并保持顺序，那么foldr是正确的变体，你可以玩一会儿，最终编写出Joseph建议的代码。然而，我同意chi的看法，直接递归是这里最好的解决方案。
map函数在这个任务中是不适用的，如果不是无法使用。 - moonGoose[] a不是一个无序的a集合，而zip只是map2(,)。 - Will NessData.List提供unfoldr，一个列表展开函数。unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr的函数接受一个种子，它要么产生一个列表元素和一个新的种子（如果maybe-value是Just），要么终止列表生成（如果它是Nothing）。展开更一般地由来自recursion-schemes的ana函数表达（"ana"是"anamorphism"的缩写）。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]
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而是用一个展开函数来实现普通的filter，那么这种笨拙将会成倍增长，正如List filter using an anamorphism中所美妙地解释的那样。span相当直接地实现filterFirst：filterFirst :: (a -> Bool) -> [a] -> [a]
filterFirst p = (\(yeas, rest) -> yeas ++ drop 1 rest) . span p
(++)重新组合列表，并删除第二部分的第一个元素（使用drop 1而不是tail，这样我们就不必为[]添加特殊情况）。另外，还有一种几乎无需点操作符的实现方式，我认为它太漂亮了，不能不提一下：filterFirst :: (a -> Bool) -> [a] -> [a]
filterFirst p = uncurry (++) . second (drop 1) . span p
虽然span是一个高阶函数，但如果您在问题的背景下发现这个实现令人失望，那也是可以理解的。毕竟，span并不比filterFirst本身更基础。难道我们不应该尝试深入一点，看看是否能够将其表达为折叠或其他递归方案的形式，以捕捉这个解决方案的精髓吗？
我认为像filterFirst这样的函数可以很好地演示hylomorphisms（即“分解-组合”模式）。Hylomorphism是一个unfold（有关详细信息，请参见我的其他答案），它生成一个中间数据结构，然后是一个fold，将此数据结构转换为其他内容。虽然看起来似乎需要两次遍历才能获得结果（一次通过输入结构，另一次通过中间结构），但如果hylomorphism正确实现（如recursion-schemes中的hylo函数所做的那样），则可以在单次遍历中完成，fold会消耗unfold生成的中间结构的部分片段（因此我们不必实际构建整个中间结构，然后再拆除它）。
{-# 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
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实现(++)所使用的方法）。
（关于BrokenList在实际应用中的类似示例，请参见我早前回答中的注释5中的breakOn实现。它说明了使用这种策略实现span所需的步骤。）
filterFirst（或者说比仅使用fold和仅使用unfold的实现更接近原始实现）。BrokenList的非融合生产和消费，可以激励使用hylo。此外，解释如何使用BrokenList比直接使用para或原始模式匹配更好（更易于理解？更容易修改？）。 - dfeuerpara解决方案也可以，而且在这种特定情况下显式递归实际上并不难理解。尽管相对冗长，但我仍然发现hylo解决方案非常透明。也许这只是一种审美感受，但我觉得看到一个数据类型捕捉算法的基本方面非常令人满意。（设计师单子foldMap解决方案以类似的方式让我感到高兴。） - duplode
deleteBy函数的用法：deleteBy (>) 1 [5,-6,-7,9,10]- melpomenefoldr编写filterFirst（和其他任何东西），但这样做会相当不优雅。使用mapAccumL可能会提供更好的结果，但在我看来，显式递归是最好的选择。 - chideleteBy (>=)，我认为...这说明了为什么将非对称函数传递给deleteBy是我要谨慎的事情。 - user11228628Maybe a的东西，然后取出Just）。如果有一个非conduit模拟的话，像Data.Conduit.List中的concatMapAccum可以做到这一点（虽然更通用，可以将1个元素发送到任意数量的结果）。 - moonGoosedeleteBy将非常适合。实际上，有人呼吁将deleteBy更改为(a -> Bool) -> [a] -> [a]...但是，除了否定谓词之外，你最终会得到filterFirst，正如OP在这里展示的那样。 - duplode