listhaskellmonad-transformersstate-monad

Filtering a List based on State in Haskell


I've been looking at the implementations of ListT to find a good way to do something like this:

func list = do
  set <- get -- Data.Set
  el <- list
  guard $ Set.notMember el set
  return el

I know I could use ListT.fromFoldable, but I want to be able to use this stream as part of a larger processing pipeline without converting from list to stream and back at every step. Perhaps something like this:

func' list = (ListT.toReverseList . ListT.take 5 . func . ListT.fromFoldable) list

From what I understand a streaming approach should be used here. But I don't understand how to do this using e.g. the list-t package. Can a traverse somehow filter out results from the stream? I don't see people asking about this so maybe the approach itself is flawed?


Solution

  • Answering the original question before the edit:

    From what I understand a streaming approach should be used here. But I don't understand how to do this using e.g. the list-t package.

    You can use regular lists if your monad is sufficiently lazy:

    import Control.Monad (filterM)
    import Control.Monad.Trans.State.Lazy (State, get)
    import Data.Set (Set, member)
    
    filterStateLazy :: Ord a => [a] -> State (Set a) [a]
    filterStateLazy = filterM $ \x -> do
        s <- get
        pure $ x `member` s
    
    -- >>> import Control.Monad.Trans.State.Lazy (evalState)
    -- >>> import qualified Data.Set as Set
    -- >>> take 5 . evalState (filterStateLazy [1..]) $ Set.fromList [1, 6, 22, 39, 54]
    -- [1,6,22,39,54]
    

    If you really want ListT though, you can use it as well and you won't need a lazy monad:

    {-# LANGUAGE FlexibleContexts #-}
    {-# LANGUAGE LambdaCase #-}
    
    import ListT
    import Control.Monad.State.Strict
    import Data.Set (Set, member)
    
    filterStateLazy :: (MonadState (Set a) m, Ord a) => ListT m a -> ListT m a
    filterStateLazy (ListT run) = ListT $ run >>= \case
        Nothing -> return Nothing
        Just (x, rest) -> do
            s <- get
            if x `member` s
                then pure $ Just (x, filterStateLazy rest)
                else uncons $ filterStateLazy rest
    
    -- >>> import Control.Monad.Trans.State.Lazy (evalState)
    -- >>> import qualified ListT as ListT
    -- >>> import qualified Data.Set as Set
    -- >>> evalState (ListT.toList . ListT.take 5 . filterStateLazy $ ListT.fromFoldable [1..]) $ Set.fromList [1, 6, 22, 39, 54]
    -- [1,6,22,39,54]