Блог

Я знаю, что есть решение для итерации через Tree using Zipper s (смотрите Подробности здесь). Хотя мне не ясно, можно ли применить ограничения памяти к этому подходу.

Контекст

Мне было предложено решить следующую проблему в Haskell:

Создайте итератор, который будет выполнять итерации по двоичному дереву по порядку.

Предположим, что двоичное дерево хранится на диске и может содержать до 10 уровней и, следовательно, может содержать до (2 ^ 10 — 1) узлов, и мы можем хранить не более 100 узлов в памяти в любой момент времени.

Цель этого итератора — загружать небольшую часть двоичного дерева с диска в память каждый раз, когда оно увеличивается, так что нам не нужно загружать все дерево в память сразу.

Я предположил, что часть памяти невозможно представить в Haskell, но мне сказали, что это неправда.

Вопрос: что можно использовать в Haskell для достижения такого поведения памяти? Приветствуются любые предложения, подходы и направления. Это просто из любопытства, я уже потерпел неудачу в решении этой проблемы.

Если итератор загружает часть дерева каждый раз, когда оно увеличивается, тогда есть два варианта:

1. Он существует в монаде ввода-вывода и работает так же, как в императивном языке.

2. Он использует лень и чередующийся ввод-вывод. Это подход, используемый такими функциями, как readFile , которые предоставляют вам все содержимое файла в виде одного отложенного списка. Фактический файл считывается по требованию, когда ваше приложение просматривает список.

Последний вариант здесь интересен.

Сложная часть отложенных списков — это фиксаторы. Предположим, ваш файл содержит список чисел. Если вы вычисляете сумму следующим образом

 nums <- map read . lines <$> readFile "numbers.txt"
putStrLn $ "The total is " <> show (sum nums)
  

тогда программа будет выполняться в постоянном пространстве. Но если вы хотите среднее:

 putStrLn $ "The average is " <> show (sum nums / fromIntegral (length nums))
  

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

(Решение состоит в том, чтобы вычислить сумму и длину параллельно в течение одного прохода. Но здесь это не относится к делу).

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

Давайте предположим, что каждый узел в файле содержит смещения в файле для левого и правого дочерних узлов. Мы можем написать функцию в монаде ввода-вывода, которая ищет смещение и считывает там узел.

 data MyNode = MyNode Int Int .....  -- Rest of data to be filled in.

readNodeData :: Handle -> Int -> IO MyNode
  

Оттуда было бы просто написать функцию, которая обходит весь файл для создания Tree MyNode . Если вы реализуете это с помощью unsafeInterleaveIO , то вы можете получить дерево, которое лениво считывается при прохождении по нему.

unsafeInterleaveIO небезопасно, потому что вы не знаете, когда будет выполнен ввод-вывод. Вы даже не знаете, в каком порядке это будет происходить, потому что это происходит только тогда, когда значение вводится принудительно во время оценки. Таким образом, это похоже на структуры «promise«, которые вы получаете в некоторых других языках. В данном конкретном случае это не проблема, потому что мы можем предположить, что файл не изменяется во время оценки.

К сожалению, это не решает проблему, потому что к моменту завершения все дерево будет храниться в памяти. Ваш обход должен сохранять корень, по крайней мере, до тех пор, пока он проходит по левой стороне, и до тех пор, пока он это делает, он будет сохранять все остальное дерево.

Решение состоит в том, чтобы переписать часть ввода-вывода, чтобы возвращать список вместо дерева, что-то вроде этого:

 readNode :: Handle -> Int -> IO [MyNode]
readNode _ (-1) = return []      -- Null case for empty child.
readNode h pos = unsafeInterleaveIO $ do
    n <- readNodeData h pos   -- Needs to be defined elsewhere.
    lefts <- readNode (leftChild n)
    rights <- readNode (rightChild n)
    return $ lefts    [n]    rights
  

Это возвращает все дерево в виде отложенного списка. По мере прохождения списка соответствующие узлы будут считываться по требованию. Пока вы не сохраняете список (см. Выше), вашей программе не нужно будет содержать ничего, кроме текущего узла и его родителей.