0

我有这个问题要做：

“定义一个函数findpath:: BTree a -> a -> Path（其中Btreea 在前面的问题中定义），给定一棵二叉树t和一个 value ，如果有一个值，则x返回从根t到叶的路径，否则返回值。运行时间你的程序应该与树中的节点数成线性关系。”xNothing

到目前为止，我有：

data Maybe a = Nothing | Just a
data BTree a = Leaf a | Fork (BTree a) (BTree a)
type Path = Maybe [Dir]
data Dir = Left | Right

findpath :: Eq a => BTree a -> a -> Path
findpath (Leaf y) x = if y==x then ??? else Nothing
findpath (Fork l r) x = nodepath (findpath l x) (findpath r x) where
   nodepath :: Path -> Path -> Path
   nodepath Nothing Nothing = Nothing
   nodepath Nothing pathr = Just [R]
   nodepath pathl Nothing = Just [L]

我仍然无法在(Leaf y)案例中构建最终答案

4

1 回答 1

13

你的语言，关于你认为程序应该做什么，向我暗示你需要帮助才能摆脱命令式思维的陷阱。让我试着提供一些帮助，基于对事物是什么的思考，而不是事物的作用。

因为findpath (Leaf y) x，你正朝着正确的方向前进。你只需要给出if一个小写字母i，然后想想什么是正确Path的Leaf。

现在，让我们考虑另一种可能性。你知道的远不止这些t。你知道你真的想弄清楚什么

findpath (Node l r) x

是（实际上是什么=），因为这是 a 的另一种可能性BTree。考虑通过询问“这是BTreea(Leaf y)还是 a (Node l r)？”来拆分问题。作为程序设计的一个概念步骤。现在，为了弄清楚上面的左侧等于什么，您有权获得一些递归计算的信息，即

findpath l x

和

findpath r x

是。如果您知道Path两者的信息l和r，您能说出Path整体Node l r的信息吗？让我用 Haskell 写下这个问题：

findpath :: Eq a => BTree a -> a -> Path
findpath (Leaf y)   x = if y==x then ??? else Nothing
findpath (Node l r) x = nodepath (findpath l x) (findpath r x) where
  nodepath :: Path -> Path -> Path
  nodepath ???

我通过引入一个辅助函数 nodepath来表达我的问题，该函数将递归计算的信息作为参数。现在您可以尝试nodepath通过模式匹配分别对左右子树的这两条路径来实现。如果您知道它们是(Just p)还是Nothing，那么您应该能够说出整个节点的路径必须是什么。

第一课，有用的思想是这样的形式：“如果这是某某，那么那一定是某某。”。存在，不做。

第二课，对数据类型进行编程的基本方法是：拆分为构造函数情况（Leafvs Node，Justvs Nothing）；通过递归调用从任何子结构中收集有用的信息；说出整个结构的价值必须是多少。

如果您遵循我的建议并弄清楚nodepath应该是什么，您可能会发现它足够简单，不值得成为一个单独的命名定义。在这种情况下，只需将nodepath调用替换为其含义并删除 -where子句。但最好从引入 开始nodepath，因为它表达了解决问题的一个有用的概念步骤。

于 2012-11-11T12:07:38.963 回答