迭代加深搜索如何在Haskell中有效地实施？

Question

我有一个要解决的优化问题。您有某种数据结构：

data Foo =
  { fooA :: Int
  , fooB :: Int
  , fooC :: Int
  , fooD :: Int
  , fooE :: Int
}

和评级功能：

rateFoo :: myFoo -> Int

我必须优化 rateFoo 通过更改结构中的值。在这种特定情况下，我决定使用 迭代加深搜索 解决问题。 （无限的）搜索树最佳优化是由另一个函数创建的，它只是将所有可能的更改递归地应用于树：

fooTree :: Foo -> Tree

我的搜索功能看起来像这样：

optimize :: Int -> Foo -> Foo
optimize threshold foo = undefined

我开始之前的问题是：

由于树可以由每个点的数据生成，因此是否只能拥有生成的树的部分，该算法当前需要这些部分？是否可以释放内存并在需要时再生树以保存内存（可以在n级中生成休假 O(n) n仍然很小，但不足以使整棵树随着时间的流逝而使整棵树在记忆中）？

这是我可以从运行时探索的东西吗？可以运行时 不了解 表达式（将评估的表达变成未评估的表达）？还是我必须为此做什么肮脏的技巧？

Answer 1

这是我的建议：

1. 只需以最直接的方式实现您的算法。
2. 轮廓。
3. 如有必要，优化速度或内存使用。

我很快了解到，我没有足够的聪明和/或经验来推理GHC会做什么或垃圾收集的工作方式。有时，我敢肯定，第一次时会灾难性地进行记忆的工作顺利进行，而且（通常是否则）看起来很简单，需要对严格注释的大惊小怪等等。

这 现实世界哈斯克尔 一章 分析和优化 一旦您进入步骤2和3，就非常有帮助。

---

例如，这是IDDF的非常简单的实现，其中 f 扩大儿童， p 是搜索谓词，以及 x 是起点。

search :: (a -> [a]) -> (a -> Bool) -> a -> Bool
search f p x = any (\d -> searchTo f p d x) [1..]
  where
    searchTo f p d x
      | d == 0    = False
      | p x       = True
      | otherwise = any (searchTo f p $ d - 1) (f x)

我通过搜索测试 "abbaaaaaacccaaaaabbaaccc" 和 children x = [x ++ "a", x ++ "bb", x ++ "ccc"] 作为 f. 。似乎很快，几乎不需要记忆（我认为与深度线性线性）。为什么不首先尝试这样的事情，然后如果不够好，然后转到更复杂的数据结构呢？

Answer 2

运行时不会不可评估表达式。

但是，有一种直接的方法可以得到您想要的东西。

考虑树的类似拉链的结构。每个节点都保留一个值和一个表示向下，向上等的thunk。右插槽中的节点）。然后，您可以控制自己坚持多少“历史”。