Haskell中用于有条件折叠列表的干净语法

Question

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

我的解决方法是编写以下helper函数，然后根据我的情况应用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]]

完成这个应该不是问题。

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的结果中丢弃最终状态
• CCD_ 18去除CCD_；现在"；值

Answer 3

让我们从使用模式匹配开始，使您自己的实现更惯用、更明显正确，而且(更快(。我们也可以以惯用的方式使用保护，而不是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语言扩展，但这样做有点烦人。