Data.Tree включает в себяunfoldTreeM_BF а такжеunfoldForestM_BF функции для построения деревьев в ширину, используя результаты монадических действий. Развертывание дерева можно легко записать с помощью развертывания леса, поэтому я сосредоточусь на последнем:

unfoldForestM_BF :: Monad m =>
             (b -> m (a, [b])) -> [b] -> m [Tree a]

Начиная со списка семян, он применяет функцию к каждому, генерируя действия, которые будут генерировать корни деревьев и семена для следующего уровня развертывания. Используемый алгоритм несколько строг, поэтому использованиеunfoldForestM_BF сIdentity монада не совсем то же самое, что использование чистогоunfoldForest, Я пытался выяснить, есть ли способ сделать это ленивым, не жертвуя егоO(n) ограниченный по времени. Если (как предложил мне Эдвард Кметт) это невозможно, мне интересно, можно ли было бы сделать это более ограниченным типом, конкретно требующимMonadFix скорее, чемMonad, Идея заключается в том, чтобы (каким-то образом) установить указатели на результаты будущих вычислений при добавлении этих вычислений в список дел, поэтому, если они ленивы в результате более ранних вычислений, они будут доступны немедленно.