Funzione come catMaybes, ma nulla contando valori

Question

Ho una lista come questa:

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

Utilizzando catMaybes posso estrarre solo i valori Just -constructed:

catMaybes foo -- [1,2,3] 

Ora sto cercando per una funzione che non produce solo un elenco di Just s ma anche un conteggio di Nothing s per un elenco finito attraversandolo una volta. Esso dovrebbe avere una firma come questo:

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

Nota: Questa domanda è stato risposto Q & A-stile e quindi volutamente non mostra alcuno sforzo di ricerca!

Answer 1

import Data.Monoid 
import Data.Foldable 

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

Answer 2

La soluzione più semplice sarebbe quello di fare semplicemente due evalutations in modo indipendente:

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

Non so se GHC è in grado di ottimizzare questo correttamente, ma la soluzione per il conteggio length . filter pNothings ha alcune peculiarità in ogni caso (vedi this SO post per una panoramica).

In teoria, questa soluzione potrebbe richiedere due passaggi sopra la lista, invece di quello

Si tratta di una soluzione ricorsiva risolvere questo problema mi si avvicinò con:

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 

Come applicarlo a un elenco dovrebbe valutare la lista solo una volta, questo dovrebbe essere più efficiente.

Tuttavia, sono preoccupato per l'anti-idioma justs ++ [v], in quanto (:) sarebbe più efficiente (vedere this discussion). Tuttavia, questo invertirà la lista risultante. Forse qualcuno con più conoscenze su questo argomento potrebbe dare un'occhiata a questo?

Si noti che questa funzione non terminerà per le liste infinite perché il conteggio Nothing non potrà mai finire per valutare.

Answer 3

userei il Writer monade:

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) 

I (++) s dovrebbero destro associato data la definizione di mapM_.

Answer 4

La mia scelta sarebbe solo un foldr:

import Control.Arrow 

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

Ci sono pro e contro per entrambe le pieghe a destra ea sinistra, in questo caso, come a destra piega rende il risultato lista correttamente pigro ed efficiente, mentre la rigida piegatura a sinistra calcola il risultato della lunghezza in modo più efficiente.

Answer 5

Possiamo avere una sinistra pieghevole per rigoroso conteggio e un diritto pieghevole per la costruzione della lista pigri allo stesso tempo:

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) 

Questo funziona per gli elenchi infiniti troppo, fintanto che non accedono al conteggio campo (snd) del risultato, mentre si calcola il conteggio in modo rigoroso ed efficiente, proprio come una variabile di accumulatore mutabile.

Answer 6

Per casi come questo, il pacchetto foldl di Gabriel Gonzalez è molto utile. Si può semplicemente utilizzare le pieghe predefiniti o definirne di personalizzate come qui sotto e combinarle utilizzando un'interfaccia applicativa:

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