2014-08-27 11 views
11

Ho una lista come questa:Funzione come catMaybes, ma nulla contando valori

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!

+4

Ancora un altro momento di usare [bella pieghevole] (http://squing.blogspot.com/2008/11 /beautiful-folding.html). –

risposta

22
import Data.Monoid 
import Data.Foldable 

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

@ AndrásKovács Bella idea! –

+1

Come la semplicità. +1 –

+1

Definitiva la soluzione più elegante, anche se mi piacciono tutti loro +1 –

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 @[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 

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.

+2

Il 'lento (++ [x])' può essere alleviato almeno a volte usando una lista di differenze. –

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_.

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.

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.

2

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 
Problemi correlati