Управление памятью хвостовых вызовов в haskell

Question

Я использую следующую структуру управления (которую я считаю хвостовой рекурсивной)

untilSuccessOrBigError :: (Eq e) => (Integer -> (Either e a)) -> Integer -> e -> (Either e a)
untilSuccessOrBigError f count bigError
  = case f count of
         Right x -> Right x
         Left e -> (if e==bigError then Left e else untilSuccessOrBigError f (count - 1) e)

делать итеративное углубление

iterativeDeepening :: (a -> [a]) -> (a -> Bool) -> (a -> Bool) -> a -> Either String a
iterativeDeepening stepFunc isAValidSolution isGraphBottom x
  = untilSuccessOrBigError
        (\count -> dfsWithMaxDepth stepFunc isAValidSolution isGraphBottom count x)
        (-1)
        "Reached graph bottom"

будет ли эта свободная память (поскольку технически она больше не сможет ее достать) как после каждого итеративного углубления, если нет, то как мне переписать управляющую структуру?

PS С другой стороны, похоже, что это не удастся, поскольку хвостовые рекурсивные структуры часто могут получить доступ к вещам в стеке, например, к добавлению к предыдущему значению, даже если это не так в этом случае. - Роман А. Тайчер, 28 ноября, 12:33. PPS В-третьих, это заставляет меня думать, что он может отбросить значения внутри dfsWithMaxDepth, как только вернется dfsWithMaxDepth, и куча ответов не займет много памяти. - Роман А. Тайчер 2 ноября

Answer 1

На первый взгляд, нет никаких причин, по которым этот мусор не будет собираться должным образом, и почему TCO не будет выполняться.

В общем, вы должны думать о tco и сборке мусора в Haskell по-другому - многие связанные с этим вопросы, перечисленные здесь на SO, кажутся полезными. По сути, вы хотите представить операционную семантику GHC Haskell как ленивое сокращение графов.

Представьте, что у вас в памяти всего AST с дополнительными стрелками от каждого использования имени до его определения, и вы запрашиваете значение "main". Теперь, чтобы получить это, вам нужно взглянуть на значение первой функции, вызванной в main, и подставить его в, что, в свою очередь, означает, что вам нужно искать следующую вещь, которую нужно оценить, и т. Д. Теперь в какой-то момент Из этого сокращения вы заметите, что вещи, на которые раньше ссылались как на выражения, теперь вычисляются и заменяются значениями, которые они представляют. Тогда эти выражения могут получить мусор. Между тем, трасса, которую вы получили от вершины графика до того, что вы сейчас оцениваете, является "стеком". Так что, если вы хотите оценить структуру, вам нужно оценить "внутри" этой структуры, то это увеличит ваш стек.

Вышесказанное небрежно и волнисто, но может помочь дать интуицию.