在 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 和某些 post 处理步骤的方法：

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]]

完成这个应该不是问题。

Answer 2

你总是可以带一些内置的机器。 Data.List 库相当强大：

import Data.List(mapAccumL)
import Data.Maybe(catMaybes)

foldrOn cond = catMaybes . snd . mapAccumL combine 0 where
  combine a el =
    if cond el then (a + 1, Nothing)
    else (0, Just (el, a))

发生了什么事

本质上，foldrOn cond是以下函数的组合：

mapAccumL combine 0 沿列表前进，通过有关最近跳过的实体数量的信息修改每个元素（从 0 开始计数，并在我们发现不匹配的内容时重置它cond 谓词）。
snd 从 mapAccumL 的结果
catMaybes 删除 Maybe 层并仅保留“当前”值。

Answer 3

让我们从使用模式匹配开始，让您自己的实现更加地道、更明显地正确，并且（快）得多。我们还可以以惯用的方式使用 guards 而不是 if/then/else；这不太重要。这里也没有理由使用 do，所以我们不会。

foldrOn _cond [] = []
foldrOn cond (hd : tl)
  | cond hd
  = case foldrOn cond tl of
      (x, y) : tl' -> (x, y + 1) : tl' 
                      -- fold token into char after it
      [] -> error "String ended on token."
  | otherwise
  = (hd, 0) : foldrOn cond tl
                      -- don't fold token

这……好吧。但正如 Will Ness 所建议的那样，我们实际上并没有通过将“不完整”元素添加到结果列表中来获得任何好处。我们可以改为计算 cond 满足条件的标记，直到我们到达块的末尾，然后生成一个完整的元素。我认为这让代码更容易理解，而且应该运行更快一点。

foldrOn cond = go 0
  where
    go count (hd : tl)
      | cond hd
      = go (count + 1) tl -- Don't produce anything; just bump the count
      | otherwise
      = (hd, count) : go 0 tl -- Produce the element and the count; reset the count to 0
    go count []
      | count == 0
      = []
      | otherwise
      = error "List ended on a token."

为了实际上 运行更快，您可能需要明确告诉编译器您确实想要计算计数。你可能还不需要理解这部分，但它看起来像这样：

-- At the top of the file, add this line:
{-# LANGUAGE BangPatterns #-}

foldrOn cond = go 0
  where
    go !count (hd : tl)
      | cond hd
      = go (count + 1) tl -- Don't produce anything; just bump the count
      | otherwise
      = (hd, count) : go 0 tl -- Produce the element and the count; reset the count to 0
    go count []
      | count == 0
      = []
      | otherwise
      = error "List ended on a token."

这可以按照 Will Ness 演示的方式写成折叠。

注意：虽然可以避免 BangPatterns 语言扩展，但这样做有点烦人。

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

Clean syntax for conditionally folding a list in Haskell

optimization

haskell

fold

conditional-statements

发生了什么事