11

我有一个这样的列表：

let foo = [Just 1, Just 2, Nothing, Just 3, Nothing, Nothing]

通过使用catMaybes，我只能提取Just-constructed 值：

catMaybes foo -- [1,2,3]

我现在正在寻找一个函数，它不仅可以生成一个Justs 列表，还可以Nothing通过遍历一次来生成一个有限列表的 s 计数。它应该有这样的签名：

catMaybesCount :: [Maybe a] -> ([a], Int)

注意：这个问题是问答式回答的，因此故意不显示任何研究工作！

4

6 回答 6

23 
import Data.Monoid
import Data.Foldable

catMaybesCount = foldMap inject where
    inject Nothing  = ([ ], Sum 1)
    inject (Just x) = ([x], Sum 0)
于 2014-08-27T19:10:52.597 回答
5

我们可以同时进行严格计数的左折叠和惰性列表构建的右折叠：

catMC :: (Num t) => [Maybe a] -> ([a], t)
catMC xs = g 0 xs 
  where 
    g !c (Nothing:xs) = g (c+1) xs 
    g !c (Just  v:xs) = let (a,b)=g c xs in (v:a,b) 
    g !c []           = ([],c)

这也适用于无限列表，只要我们不访问snd结果的计数字段 ()，同时以严格、有效的方式计算计数，就像可变累加器变量一样。

于 2014-08-27T21:30:22.493 回答
4

我的选择只是foldr：

import Control.Arrow

catMaybesCount :: [Maybe a] -> ([a], Int)
catMaybesCount = foldr (maybe (second succ) (first . (:))) ([], 0)

在这种情况下，左右折叠各有利弊，因为右折叠使列表结果适当地惰性和高效，而严格的左折叠更有效地计算长度结果。

于 2014-08-27T19:11:59.283 回答
3

我会使用Writer单子：

import Control.Arrow ( (***) )
import Data.Monoid ( Sum(..) )
import Control.Monad.Writer ( execWriter, tell )

catMaybesCount xs = (id *** getSum) $ execWriter (mapM_ go xs)
   where
      go (Just v) = tell ([v], Sum 0)
      go Nothing = tell ([], Sum 1)

给定的(++)定义，s 应该右关联mapM_。

于 2014-08-27T18:54:56.530 回答
2

最天真的解决方案是简单地独立进行两个评估：

catMaybesCount :: [Maybe a] -> ([a], Int)
catMaybesCount xs = (catMaybes xs, length $ filter isNothing xs)

我不知道 GHC 是否能够正确优化这一点，但无论如何length . filter p计数的解决方案Nothings都有一些特殊性（请参阅此 SO 帖子以获取概述）。

从理论上讲，此解决方案可能需要两次遍历列表，而不是一次

这是解决我提出的这个问题的递归解决方案：

import Data.Maybe

-- | Equivalent to @catMaybes@, but additonally counts @Nothing@ values
catMaybesCount :: [Maybe a] -> ([a], Int)
catMaybesCount xs =  catMaybesCountWorker xs [] 0

-- | Worker function for @catMaybesCount@   
catMaybesCountWorker :: [Maybe a] -> [a] -> Int -> ([a], Int)
catMaybesCountWorker [] justs cnt = (justs, cnt)
catMaybesCountWorker (Nothing:xs) justs cnt =
    catMaybesCountWorker xs justs (cnt + 1)
catMaybesCountWorker ((Just v):xs) justs cnt =
    catMaybesCountWorker xs (justs ++ [v]) cnt

由于将其应用于列表应该只评估一次列表，这应该更有效。

但是我担心justs ++ [v]反成语，因为它(:)会更有效（见这个讨论）。但是，这会反转结果列表。也许对这个主题有更多了解的人可以看看它？

请注意，此函数不会因无限列表而终止，因为Nothing计数永远不会完成评估。

于 2014-08-27T18:37:53.103 回答
2

对于这种情况，Gabriel Gonzalez 的foldl包非常方便。您可以简单地使用预定义的折叠或定义如下的自定义折叠，并使用应用界面将它们组合起来：

import qualified Control.Foldl as L
import Control.Applicative ((<$>),(<*>))
import Data.Monoid
import qualified Data.DList as DL

catMaybesCount :: [Maybe a] -> ([a], Int)
catMaybesCount = L.fold $ (,) <$> elemJust <*> countJust

-- L.Fold :: (x -> a -> x) -> x -> (x -> b) -> L.Fold a b

elemJust :: L.Fold (Maybe a) [a]
elemJust = L.Fold step DL.empty DL.toList
  where step xs (Just x) = DL.snoc xs x
        step xs Nothing = xs

countJust :: L.Fold (Maybe a) Int
countJust = L.Fold step (Sum 0) getSum
  where step acc (Just _) = acc
        step acc Nothing = acc <> Sum 1
于 2014-08-29T18:19:45.427 回答