用 Haskell 广度优先构建二叉树(非 BST) [英] Building a Binary Tree (not BST) in Haskell Breadth-First
问题描述
我最近开始使用 Haskell，它可能会持续使用一段时间..只是被要求使用它来更好地理解我在 Uni 上的课程的函数式编程.
I recently started using Haskell and it will probably be for a short while. Just being asked to use it to better understand functional programming for a class I am taking at Uni.
现在我在尝试做的事情上遇到了一个小问题.我想以广度优先来构建它，但我认为我的条件搞砸了，或者我的条件也错了.
Now I have a slight problem I am currently facing with what I am trying to do. I want to build it breadth-first but I think I got my conditions messed up or my conditions are also just wrong.
所以基本上如果我给它[A1-Gate"、North-Region"、South-Region"、Convention Center"、Rectorate"、Academic Building1"、Academic Building2"] 和 [0.0, 0.5, 0.7, 0.3, 0.6, 1.2, 1.4, 1.2]，我的树应该像
So essentially if I give it
["A1-Gate", "North-Region", "South-Region", "Convention Center", "Rectorate", "Academic Building1", "Academic Building2"] and [0.0, 0.5, 0.7, 0.3, 0.6, 1.2, 1.4, 1.2], my tree should come out like
但是我的测试运行结果哈哈不是我所期望的.因此，Haskell 方面的一位特别敏锐的专家可能会帮助我发现我做错了什么.输出:
But my test run results are haha not what I expected. So an extra sharp expert in Haskell could possibly help me spot what I am doing wrong. Output:
*Main> l1 = ["A1-Gate", "North-Region", "South-Region", "Convention Center",
"Rectorate", "Academic Building1", "Academic Building2"]
*Main> l3 = [0.0, 0.5, 0.7, 0.3, 0.6, 1.2, 1.4, 1.2]
*Main> parkingtree = createBinaryParkingTree l1 l3
*Main> parkingtree
Node "North-Region" 0.5
(Node "A1-Gate" 0.0 EmptyTree EmptyTree)
(Node "Convention Center" 0.3
(Node "South-Region" 0.7 EmptyTree EmptyTree)
(Node "Academic Building2" 1.4
(Node "Academic Building1" 1.2 EmptyTree EmptyTree)
(Node "Rectorate" 0.6 EmptyTree EmptyTree)))
A-1 Gate 应该是根，但它最终成为一个没有孩子的孩子，条件非常混乱.
A-1 Gate should be the root but it ends up being a child with no children so pretty messed up conditions.
如果我能得到一些指导，它会有所帮助.以下是我到目前为止所写的内容::
If I could get some guidance it would help. Below is what I've written so far::
data Tree = EmptyTree | Node [Char] Float Tree Tree deriving (Show,Eq,Ord)
insertElement location cost EmptyTree =
Node location cost EmptyTree EmptyTree
insertElement newlocation newcost (Node location cost left right) =
if (left == EmptyTree && right == EmptyTree)
then Node location cost (insertElement newlocation newcost EmptyTree)
right
else if (left == EmptyTree && right /= EmptyTree)
then Node location cost (insertElement newlocation newcost EmptyTree)
right
else if (left /= EmptyTree && right == EmptyTree)
then Node location cost left
(insertElement newlocation newcost EmptyTree)
else Node newlocation newcost EmptyTree
(Node location cost left right)
buildBPT [] = EmptyTree
--buildBPT (xs:[]) = insertElement (fst xs) (snd xs) (buildBPT [])
buildBPT (x:xs) = insertElement (fst x) (snd x) (buildBPT xs)
createBinaryParkingTree a b = buildBPT (zip a b)
感谢您提供的任何指导.是的，我已经查看了一些的类似问题，我确实认为我的问题有所不同，但是如果您认为某个帖子有明确的答案可以帮助我愿意去看看它.
Thank you for any guidance that might be provided. Yes I have looked at some of the similar questions I do think my problem is different but if you think a certain post has a clear answer that will help I am willing to go and take a look at it.
推荐答案
这是一个 corecursive 解决方案.
Here's a corecursive solution.
{-# bft(Xs,T) :- bft( Xs, [T|Q], Q). % if you don't read Prolog, see (*)
bft( [], Nodes , []) :- maplist( =(empty), Nodes).
bft( [X|Xs], [N|Nodes], [L,R|Q]) :- N = node(X,L,R),
bft( Xs, Nodes, Q).
#-}
data Tree a = Empty | Node a (Tree a) (Tree a) deriving Show
bft :: [a] -> Tree a
bft xs = head nodes -- Breadth First Tree
where
nodes = zipWith g (map Just xs ++ repeat Nothing) -- values and
-- Empty leaves...
(pairs $ tail nodes) -- branches...
g (Just x) (lt,rt) = Node x lt rt
g Nothing _ = Empty
pairs ~(a: ~(b:c)) = (a,b) : pairs c
{-
nodes!!0 = g (Just (xs!!0)) (nodes!!1, nodes!!2) .
nodes!!1 = g (Just (xs!!1)) (nodes!!3, nodes!!4) . .
nodes!!2 = g (Just (xs!!2)) (nodes!!5, nodes!!6) . . . .
................ .................
-}
nodes 是结果树所有子树的广度优先枚举.树本身是顶部子树，即此列表中的第一个.我们从输入 xs 中的每个 x 创建 Nodes，当输入累了，我们通过使用无限数量的 Nothing 来创建 Empty s(Empty 叶子的真实长度是 length xs +1 但我们不需要关心那个).
nodes is the breadth-first enumeration of all the subtrees of the result tree. The tree itself is the top subtree, i.e., the first in this list. We create Nodes from each x in the input xs, and when the input
is exhausted we create Emptys by using an indefinite number of Nothings instead (the Empty leaves' true length is length xs + 1 but we don't need to care about that).
我们根本不用数.
测试:
> bft [1..4]
Node 1 (Node 2 (Node 4 Empty Empty) Empty) (Node 3 Empty Empty)
> bft [1..10]
Node 1
(Node 2
(Node 4
(Node 8 Empty Empty)
(Node 9 Empty Empty))
(Node 5
(Node 10 Empty Empty)
Empty))
(Node 3
(Node 6 Empty Empty)
(Node 7 Empty Empty))
它是如何工作的:关键是 g 的懒惰，它不强制 lt 的，也不是 rt 的值，而元组结构很容易由 - 本身非常懒惰 - pairs 提供.因此，当用作 g 的第二个和第三个参数时，它们就像 Prolog 伪代码 (*) 中的 not-yet-set variables 一样.但是，对于 xs 中的下一个 x，this lt 引用的节点变成了 g 的 result 的 next 调用.
How does it work: the key is g's laziness, that it doesn't force lt's nor rt's value, while the tuple structure is readily served by -- very lazy in its own right -- pairs. So both are just like the not-yet-set variables in that Prolog pseudocode(*), when served as 2nd and 3rd arguments to g. But then, for the next x in xs, the node referred to by this lt becomes the next invocation of g's result.
然后轮到rt，等等.当xs结束，我们点击Nothings，g 完全停止从 pairs 的输出中提取值.所以 pairs 也停止在 nodes 上前进，因此它永远不会完成，尽管它被定义为过去那个点的 Empty 无休止的流，只是为了安全起见.
And then it's rt's turn, etc. And when xs end, and we hit the Nothings, g stops pulling the values from pairs's output altogether. So pairs stops advancing on the nodes too, which is thus never finished though it's defined as an unending stream of Emptys past that point, just to be on the safe side.
(*) Prolog 的变量明确 设置-once:允许它们处于 not-yet-assigned 状态.Haskell 的 (x:xs) 是 Prolog 的 [X |Xs].
(*) Prolog's variables are explicitly set-once: they are allowed to be in a not-yet-assigned state. Haskell's (x:xs) is Prolog's [X | Xs].
伪代码:维护一个队列；排队未分配的指针"；对于 xs 中的每个 x: { 将当前队列头部的指针设置为 Node(x, lt, rt) where lt, rt 是未赋值的指针；入队 lt;入队 rt;弹出队列 };将队列中剩余的所有指针设置为Empty；在队列的原始头部找到结果树，即原始第一个未分配指针"(或空框"而不是未分配指针"是另一种选择).
The pseudocode: maintain a queue; enqueue "unassigned pointer"; for each x in xs: { set pointer in current head of the queue to Node(x, lt, rt) where lt, rt are unassigned pointers; enqueue lt; enqueue rt; pop queue }; set all pointers remaining in queue to Empty; find resulting tree in the original head of the queue, i.e. the original first "unassigned pointer" (or "empty box" instead of "unassigned pointer" is another option).
这个 Prolog 的队列"当然是完全持久的:popping"不会改变任何数据结构，也不会改变对队列前头的任何未完成的引用——它只是将当前指针推进到队列中.所以在所有这些排队之后剩下的是构建树节点的bfs-enumeration，树本身是它的头元素——树是它的顶部节点，两个子节点在枚举完成时完全实例化到底部叶子.
This Prolog's "queue" is of course fully persistent: "popping" does not mutate any data structure and doesn't change any outstanding references to the queue's former head -- it just advances the current pointer into the queue. So what's left in the wake of all this queuing, is the bfs-enumeration of the built tree's nodes, with the tree itself its head element -- the tree is its top node, with the two children fully instantiated to the bottom leaves by the time the enumeration is done.
更新: @dfeuer 提出了大大简化的 版本 它更接近 Prolog 原始版本(帖子顶部评论中的那个)，可以更 更清晰.在他的帖子中寻找更高效的代码和讨论以及其他内容.使用简单的 [] 而不是 dfeuer 使用更高效的无限流类型 data IS a = a :+ IS a 用于子树队列，它变成了>
Update: @dfeuer came up with much simplified version of it which is much closer to the Prolog original (that one in the comment at the top of the post), that can be much clearer. Look for more efficient code and discussion and stuff in his post. Using the simple [] instead of dfeuer's use of the more efficient infinite stream type data IS a = a :+ IS a for the sub-trees queue, it becomes
bftree :: [a] -> Tree a
bftree xs = t
where
t : q = go xs q
go [] _ = repeat Empty
go (x:ys) ~(l : ~(r : q)) = Node x l r : go ys q
---READ-- ----READ---- ---WRITE---
{-
xs = [ x x2 x3 x4 x5 x6 x7 x8 … ]
(t:q) = [ t l r ll lr rl rr llr … Empty Empty … … ]
-}
为了比较，树的广度优先枚举的相反操作是
For comparison, the opposite operation of breadth-first enumeration of a tree is
bflist :: Tree a -> [a]
bflist t = [x | Node x _ _ <- q]
where
q = t : go 1 q
go 0 _ = []
go i (Empty : q) = go (i-1) q
go i (Node _ l r : q) = l : r : go (i+1) q
-----READ------ --WRITE--
bftree 是如何工作的:t : q 是树的子树以广度优先顺序的列表.go (x:ys) 的特定调用使用了 l 和 r before 它们由随后的调用定义go，或者在 ys 后面使用另一个 x，或者通过 go [] 总是返回 空.结果 t 是这个列表中的第一个，树的最顶层节点，即树本身.
How does bftree work: t : q is the list of the tree's sub-trees in breadth-first order. A particular invocation of go (x:ys) uses l and r before they are defined by subsequent invocations of go, either with another x further down the ys, or by go [] which always returns Empty. The result t is the very first in this list, the topmost node of the tree, i.e. the tree itself.
这个树节点列表由go的递归调用创建，其速度与输入值列表xs相同被消耗，但作为go的输入以两倍的速度被消耗，因为每个节点有两个子节点.
This list of tree nodes is created by the recursive invocations of go at the same speed with which the input list of values xs is consumed, but is consumed as the input to go at twice that speed, because each node has two child nodes.
因此也必须定义这些额外的节点，因为 Empty 离开.我们不关心需要多少，只需创建一个无限列表来满足任何需要，尽管空叶子的实际数量将比 xs 多一个.
These extra nodes thus must also be defined, as Empty leaves. We don't care how many are needed and simply create an infinite list of them to fulfill any need, although the actual number of empty leaves will be one more than there were xs.
这实际上与计算机科学中数十年来用于数组支持树的方案相同，其中树节点以广度优先顺序放置在线性数组中.奇怪的是，在这样的设置中，两种转换都是无操作——只有我们对相同数据的解释是变化的，我们对它的处理，我们如何与/使用它.
This is actually the same scheme as used in computer science for decades for array-backed trees where tree nodes are placed in breadth-first order in a linear array. Curiously, in such setting both conversions are a no-op -- only our interpretation of the same data is what's changing, our handling of it, how are we interacting with / using it.
这篇关于用 Haskell 广度优先构建二叉树(非 BST)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
