I have a scenario of traversing a non-deterministic search space, with an upper bound on the number of visits. Using ListT (State Int) a
, I have managed to achieve this.
My expectation was that, applying take 1
on the result would prevent subsequent traversal of the tree once the first solution is reached. This is because Control.Monad.Trans.State
is said to be lazy, and I am using list-t
which is "A correct implementation of the list monad-transformer. Useful for basic streaming."
However, this toy program proves me wrong:
import qualified Data.List as L
import Data.Maybe
import Control.Monad
import Control.Monad.Trans.Class
import Control.Monad.Trans.State
import qualified ListT as LT
import Debug.Trace
dictionary = ["aabb","aa","bb"]
parse :: String -> [[String]]
parse = take 1 . flip evalState 0 . LT.toList . go [] where
go :: [String] -> String -> LT.ListT (State Int) [String]
go ac "" = trace ("trace: " ++ show ac) (return ac)
go ac input = do
callCount <- lift get
if callCount >= 10 then trace "overflow" mzero else do
nextWord <- LT.fromFoldable $ filter (`L.isPrefixOf` input) dictionary
let rest = fromJust $ L.stripPrefix nextWord input
lift $ modify (+1)
go (nextWord:ac) rest
Output:
ghci> parse "aabb"
trace: ["aabb"]
trace: ["bb","aa"] -- Why this line at all?
[["aabb"]]
So, what am I missing, and how can we leverage laziness to exit after the first match?
PS: I don't like the solution of repurposing the state:
go ac "" = do
lift modify (const 10)
return ac
The thing you're missing is here:
parse = take 1 . flip evalState 0 . LT.toList . go [] where
^^^^^^^^^
toList
is not lazy in the monadic effects. Try head
instead:
parse :: String -> Maybe [String]
parse = flip evalState 0 . LT.head . go [] where
More generally, control of how much of the result you consume must be done with ListT
functions, not Data.List
functions.