haskell - 在 Haskell 中有条件地折叠列表的简洁语法

Question

我对 haskell 比较陌生，但在搜索中我找不到有条件折叠列表的简单方法。即当一个元素满足一个条件(如在 filter 中)以通过函数折叠该元素时(如 foldr 和 foldl)。

我的解决方法是编写以下辅助函数，然后应用 map 以根据我的情况更改结果对列表。

-- This function returns tuples containing the elements which 
--    satisfy `cond` folded right, adding 1 to the second value
-- in each pair. (`snd` pair starts at 0)
-- Condition takes a single value (similar to `filter`)
-- NOTE: list cannot end with token
foldrOn cond list = 
    if (length list) > 0 then 
        if cond (head list) then 
            do
                let tmp = foldrOn cond (tail list)
                (fst (head tmp), snd (head tmp) + 1) : (tail tmp) 
                      -- fold token into char after it 
        else
            (head list, 0) : (foldrOn cond (tail list)) 
                      -- don't fold token
    else
        [] -- base case len list = 0

foldlOn cond list = ...

例如，用例类似于想要删除以下列表中的零，但请记住每个值之间删除了多少。

-- the second value in each resultant pair represents the number of 
-- zeroes preceding the corresponding first value in the original list.
foldrOn (== 0) [1,0,0,0,0,0,1,0,0,0,1] -- [(1,0),(1,5),(1,3)]
foldrOn (== 0) [1,0,0,12,0,13] -- [(1,0),(12,2),(13,1)]

有没有更好的方法来做到这一点？此外，这可以做得更优化吗？

Answer 1

首先，

foldrOn :: Num t => (a -> Bool) -> [a] -> [(a, t)]
-- foldrOn (== 0) [1,0,0,0,0,0,1,0,0,0,1] -- [(1,0),(1,5),(1,3)]
foldrOn p xs  =  foldr g [] xs
  where
  g x []        = [(x,0)]
  g x ((y,n):r)
    | p x       = ((y,n+1):r)
  g x r         = ((x,0):r)

这是最简单的，虽然它是递归的，即在开始返回结果之前将整个列表强制到末尾。

为了使其最大程度地惰性，我们必须使用惰性左折叠。跳过满足 p 的元素仍然是一个递归步骤，但至少该过程将在每个这样的跨度之间暂停。

惰性左折叠通常实现为 foldr 附加参数沿列表从左到右传递:

foldlOn :: Num t => (a -> Bool) -> [a] -> [(a, t)]
-- foldlOn (== 0) [1,0,0,0,0,0,1,0,0,0,1] -- [(1,0),(1,5),(1,3)]
foldlOn p xs  =  foldr g z xs 0
  where
  g x r i | p x       =         r (i+1)
          | otherwise = (x,i) : r 0
  z    _i             =         []

或者你可以结合 span/break 和 unfoldr 来做同样的事情。

您可能会找到一种方法来使用 groupBy 和一些后处理步骤:

GHCi> groupBy (\a b -> (==0) b) [1,0,0,0,0,0,1,0,0,0,1]
[[1,0,0,0,0,0],[1,0,0,0],[1]]

GHCi> groupBy (const (==0)) [1,2,0,0,1,0,1]
[[1],[2,0,0],[1,0],[1]]

完成这应该不是问题。