1

我有两个类似于filter和的功能takeWhile。

filterAcc, takeWhileAcc :: ([a] -> Bool) -> [a] -> [a]
filterAcc p xs = go xs []
    where go [] acc     = acc
          go (x:xs) acc
            | p (x:acc) = go xs (x:acc)
            | otherwise = go xs acc

takeWhileAcc p xs = go xs []
    where go [] acc     = acc
          go (x:xs) acc
            | p (x:acc) = go xs (x:acc)
            | otherwise = acc

它们都采用谓词和列表，它们与常规的不同之处filter在于takeWhile谓词将累积的结果作为输入。

我的问题是，虽然filter even [1..]会立即（懒惰地）开始产生输出，但会filterAcc (any even) [1..]挂起。我的怀疑是辅助函数go正在阻止这些函数懒惰地行动。

我怎样才能让这些功能懒惰地运行？

4

2 回答 2

6

问题是 cons 的情况go总是以对自身的尾调用结束。它只在到达列表末尾时返回有用的东西，这当然不会发生在无限列表中。

相反，您应该随时返回元素：

filterAcc, takeWhileAcc :: ([a] -> Bool) -> [a] -> [a]
filterAcc p xs = go xs []
    where go [] acc     = []
          go (x:xs) acc
            | p (x:acc) = x : go xs (x:acc)
            | otherwise = go xs acc

takeWhileAcc p xs = go xs []
    where go [] acc     = []
          go (x:xs) acc
            | p (x:acc) = x : go xs (x:acc)
            | otherwise = []
于 2012-11-21T04:24:04.253 回答
1

惰性列表消费通常是通过foldr.

您的累加器需要从左到右的信息流。这通常是通过使用来实现的foldl，但这意味着严格的列表消费。

解决方案是使用scanl：

--- mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
--- scanl     :: (a   -> b -> a)        -> a   -> [b] -> [a]

takeWhileAcc p []     = []
takeWhileAcc p (x:xs) = map snd $ takeWhile (p.fst) 
                                $ scanl (\(acc,_) y-> (y:acc,y)) ([x],x) xs

filterAcc p []        = []
filterAcc p (x:xs)    = map snd $ filter (p.fst) 
                                $ scanl (\(acc,_) y-> (y:acc,y)) ([x],x) xs

另一种可能性是使用until, 或mapAccumL。后者很自然，只是它不收集累加值，而是传递最后一个累加器值。

于 2012-11-21T14:32:34.713 回答