Как перебрать дерево с ограничением памяти в Haskell? - PullRequest
Новая
       13

Как перебрать дерево с ограничением памяти в Haskell?

2 голосов
/ 24 апреля 2019

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

Контекст

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

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

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

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

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

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

1 Ответ

2 голосов
/ 24 апреля 2019

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

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

  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 небезопасно, потому что вы не знаете, когда будет выполнен IO. Вы даже не знаете, в каком порядке это произойдет, потому что это происходит только тогда, когда значение форсируется во время оценки. Таким образом, это похоже на структуру " обещание ", которую вы получаете на некоторых других языках. В данном конкретном случае это не проблема, поскольку мы можем предположить, что файл не изменяется во время оценки.

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

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

readNode :: Handle -> Int -> IO [MyNode]
readNode _ (-1) = []      -- 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

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

...