Filtering a List based on State in Haskell

Question

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?

Answer 1

While @effectfully's answer works fine, you're probably looking for mfilter from Control.Monad:

func :: (MonadPlus m, MonadState (Set a) m, Ord a) => m a -> m a
func act = do
  st <- get
  mfilter (`Set.notMember` st) act

If your filtering function is itself monadic, then you might need to define your own:

mfilterM :: (MonadPlus m) => (a -> m Bool) -> m a -> m a
mfilterM f act = do
  a <- act
  b <- f a
  if b then pure a else empty

which, for example, would let you write a function that filters out the list of values seen so far, keeping the set of previous values in the state:

unique :: (MonadPlus m, MonadState (Set a) m, Ord a) => m a -> m a
unique = mfilterM firstTime
  where firstTime x = do
          isnew <- gets (Set.notMember x)
          when isnew $ modify (Set.insert x)
          pure isnew

In context, and borrowing @effectfully's example:

import ListT
import Control.Monad
import Control.Monad.State
import Control.Applicative
import Data.Set (Set)
import qualified Data.Set as Set

func1 :: (MonadPlus m, MonadState (Set a) m, Ord a) => m a -> m a
func1 act = do
  st <- get
  mfilter (`Set.notMember` st) act

mfilterM :: (MonadPlus m) => (a -> m Bool) -> m a -> m a
mfilterM f act = do
  a <- act
  b <- f a
  if b then pure a else empty

unique :: (MonadPlus m, MonadState (Set a) m, Ord a) => m a -> m a
unique = mfilterM firstTime
  where firstTime x = do
          isnew <- gets (Set.notMember x)
          when isnew $ modify (Set.insert x)
          pure isnew

runM :: ListT (State (Set a)) a -> Set a -> [a]
runM act state0 = evalState (ListT.toList act) state0

main :: IO ()
main = do
  print $ runM (ListT.take 5 . func1 . ListT.fromFoldable $ [1..]) (Set.fromList [1,6,22,39,54])
  print $ runM (unique . ListT.fromFoldable $ [1,2,3,4,5,1,3,6,5,7]) (Set.empty)

Answer 2

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]