Функция, например catMaybes, но подсчет значений Nothing

У меня есть список вроде этого:

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

Используя catMaybes, я могу извлечь только значения Just -constructed:

catMaybes foo -- [1,2,3]

Теперь я ищу функцию, которая не только дает список Just, но и счетчик Nothing для конечного списка, пройдя его один раз. Он должен иметь такую подпись:

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

Примечание. На этот вопрос был дан ответ Q & A-style и, следовательно, намеренно не показывает никаких исследований!

Ответ 1

import Data.Monoid
import Data.Foldable

catMaybesCount = foldMap inject where
    inject Nothing  = ([ ], Sum 1)
    inject (Just x) = ([x], Sum 0)

Ответ 2

Мы можем иметь левую фальцовку для строгой подсчета и правильное складывание для создания ленивого списка в одно и то же время:

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)

Это также работает для бесконечных списков, если мы не получаем доступ к полю count (snd) результата при вычислении счета строгим, эффективным образом, подобно изменчивой переменной аккумулятора.

Ответ 3

Мой выбор будет всего лишь foldr:

import Control.Arrow

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

В этом случае есть плюсы и минусы как для левого, так и для правого сгибов, так как правая сглаженность делает результат списка ленивым и эффективным, а строгая левая складка более эффективно вычисляет результат длины.

Ответ 4

Я бы использовал монаду 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)

(++) должен правильно ассоциироваться с определением mapM_.

Ответ 5

Наиболее наивным решением было бы просто выполнить обе эвалютации самостоятельно:

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

Я не знаю, сможет ли GHC оптимизировать это правильно, но решение length . filter p для подсчета Nothings имеет некоторые особенности (см. этот SO post для обзора).

Теоретически это решение может потребовать двух проходов над списком, вместо одного

Это рекурсивное решение, разрешающее эту проблему, с которой я столкнулся:

import Data.Maybe

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

-- | Worker function for @[email protected]   
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 никогда не закончит оценку.

Ответ 6

В подобных случаях пакет 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