11

次のようなリストがあります。

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

を使用すると、構築された値catMaybesのみを抽出できます。Just

catMaybes foo -- [1,2,3]

私は今、 s のリストを生成するだけでなく、一度走査することで有限リストの s のJust数も生成する関数を探しています。Nothing次のような署名が必要です。

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

注:この質問は Q&A スタイルで回答されているため、意図的に研究努力を示していません。

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 に答える
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)

の(++)定義を考えると、 は右結合する必要があり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 の投稿を参照してください)。

理論的には、このソリューションでは、リストに対して 1 回ではなく 2 回のパスが必要になる可能性があります。

これは、私が思いついたこの問題を解決する再帰的なソリューションです。

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 に答える