使用ListT (State Int)未实现惰性求值，如何在首个匹配后终止遍历？

我用ListT (State Int) a实现了一个带访问次数上限的非确定性搜索空间遍历，原本以为对结果用take 1取首个解后，程序会停止后续的树遍历——毕竟Control.Monad.Trans.State是惰性的，而且我用的list-t是官方宣称的「正确列表monad转换器，适用于基础流处理」。但测试结果却不符合预期：

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

测试输出：

ghci> parse "aabb"
trace: ["aabb"]
trace: ["bb","aa"]   -- 为什么会出现这一行？
[["aabb"]]

我忽略了什么？怎么利用惰性在找到首个匹配后就退出？另外我不想用这种重置状态的 workaround：

go ac "" = do
  lift $ modify (const 10)
  return ac

问题根源：调用顺序搞反了 #

你当前的写法是先把整个ListT转换成完整列表，再取第一个元素：
take 1 . flip evalState 0 . LT.toList

这里的关键是：LT.toList会遍历ListT的所有分支，执行每个分支对应的State计算，把所有结果收集成列表后，才会执行take 1。也就是说，哪怕你只需要第一个解，所有搜索分支的计算还是会被完整执行，这就导致了第二个trace输出。

list-t的惰性特性，需要你在ListT monad内部提前终止，而不是等所有结果生成后再截断。

解决方法：在ListT层面取首个元素 #

调整调用顺序，用LT.take 1在ListT转换器内部只保留第一个结果，再执行State计算：

修改后的parse函数：

parse :: String -> [[String]]
parse input = flip evalState 0 . LT.toList $ LT.take 1 (go [] input)

测试输出就会符合预期：

ghci> parse "aabb"
trace: ["aabb"]
[["aabb"]]

原理说明 #

LT.take 1会让ListT在生成第一个结果后，立即停止遍历后续的分支。此时LT.toList只会执行第一个分支的State计算，不会触发第二个分支（即匹配"aa"的分支），自然就不会出现多余的trace输出。

State的惰性在这里没有问题，问题出在你没有利用list-t的流处理特性提前截断，而是等所有分支执行完再做截断。

内容的提问来源于stack exchange，提问作者cobra