我知道有一个使用Tree
s迭代Zipper
的解决方案(详见here)。虽然我不清楚是否有可能对这种方法应用内存限制。
我在Haskell中遇到了以下问题需要解决:
设计一个迭代器,它将按顺序迭代二叉树。
假设二叉树存储在磁盘上,最多可包含10个级别,因此最多可包含(2 ^ 10 - 1)个节点,并且我们可以在任何给定时间在内存中存储最多100个节点。
这个迭代器的目标是在每次递增时将二进制树的一小部分从磁盘加载到内存,这样我们就不需要一次将整个树加载到内存中。
我假设内存部分不可能在Haskell中表示,但我被告知这不是真的。
问题:在Haskell中可以使用什么来实现内存行为?任何建议,方法和方向表示赞赏。这只是出于好奇,我已经无法解决这个问题了。
如果迭代器每次递增时都会加载树的一部分,那么有两个选项:
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))
然后程序将整个文件加载到内存中。这是因为它必须遍历列表两次,一次计算总和,一次计算长度。它只能通过保存整个列表来实现。
(解决方案是在一次通过中并行计算总和和长度。但这不是这里的重点)。
您提出的树问题的挑战是提出一种迭代方法,避免保留树。
让我们假设文件中的每个节点都包含左右子节点的文件中的偏移量。我们可以在IO monad中编写一个函数,它寻求偏移并读取那里的节点。
data MyNode = MyNode Int Int ..... -- Rest of data to be filled in.
readNodeData :: Handle -> Int -> IO MyNode
从那里编写一个遍历整个文件以创建Tree MyNode
的函数会很简单。如果你使用unsafeInterleaveIO
实现这个,那么你可以获得一个在遍历时懒惰读取的树。
unsafeInterleaveIO
是不安全的,因为你不知道何时完成IO。你甚至不知道它会发生什么样的顺序,因为它只发生在评估期间强制值的时候。通过这种方式,它就像你在其他语言中得到的“promise”结构一样。在这种特殊情况下,这不是问题,因为我们可以假设文件在评估期间不会发生变化。
不幸的是,这并没有解决问题,因为整个树将在你完成时保存在内存中。你的遍历必须保留根,至少只要它穿过左侧,并且只要它这样做它将保留树的其余部分。
解决方案是重写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
这将整个树作为惰性列表返回。当您遍历列表时,将按需读取相关节点。只要您不保留列表(参见上文),您的程序就不需要保存除当前节点及其父节点之外的任何内容。