Haskell. Not seeing laziness despite using list-t's ListT (State s)

Question

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

Answer 1

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.