哈斯克尔。尽管使用了 list-t 的 ListT (State s)，但没有看到惰性

Question

我有一个遍历非确定性搜索空间的场景，访问次数有上限。使用

ListT (State Int) a

，我成功实现了这一目标。

我的期望是，在结果上应用

take 1

将阻止在达到第一个解决方案后对树进行后续遍历。这是因为

Control.Monad.Trans.State

据说很懒，而我正在使用

list-t

，它是“列表 monad-transformer 的正确实现。对于基本流式处理很有用。”

但是，这个玩具程序证明我错了：

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"]   -- Why this line at all?
[["aabb"]]

那么，我错过了什么，我们如何利用懒惰在第一场比赛后退出？

PS：我不喜欢重新利用状态的解决方案：

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

Answer 1

你缺少的东西在这里：

parse = take 1 . flip evalState 0 . LT.toList . go [] where
                                    ^^^^^^^^^

toList

在单子效果方面并不懒惰。尝试使用

head

来代替：

parse = flip evalState 0 . LT.head . go [] where

更一般地说，控制消耗的结果量必须使用

ListT

函数，而不是

Data.List

函数。