在Haskell广度优先中构建二叉树(不是BST) [英] Building a Binary Tree (not BST) in Haskell Breadth-First
问题描述
我最近开始使用Haskell，它可能会出现 short 一阵子.只是被要求使用它来更好地理解我在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门应该是根，但最终会是一个没有孩子的孩子，所以情况很糟.
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 解决方案.
{-# 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)
-- true length of Empty leaves: |xs| + 1
(pairs $ tail nodes)
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创建一个Node，当输入
筋疲力尽，我们创建了Empty s.
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.
我们根本不必数数.
测试:
> 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.因此，两者都用作Prolog伪代码(*)中的尚未设置变量，当用作g的第二和第三参数时.但是，对于xs中的下一个x，由 this lt引用的节点将成为
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结束并按下Nothing时，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的变量明确地显示 设置-一次:允许它们处于尚未分配状态. 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)，其中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).
此序言的队列"当然是完全持久的:不会更改任何数据结构，也不会更改对队列的前头的任何未完成引用-只是将当前指针前进到队列中.因此，所有这些排队之后剩下的就是已构建树的节点的 bfs枚举，其中树本身是head元素-树是节点，在枚举完成时两个孩子完全实例化到底部的叶子.
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 提出了许多简化的他的帖子中查找更有效的代码和讨论以及更多内容.使用简单的[]而不是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---
为进行比较，一棵树的广度优先枚举的相反操作是
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 之前的，它们是由随后的go调用定义的，可以是ys后面的另一个x或go []总是返回Empty.结果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.
这实际上与计算机科学数十年来用于阵列支持树的方案相同，在阵列树中，树节点在线性阵列中以广度优先顺序放置.奇怪的是，在这种情况下，两个转换都是 no-op －只有我们对相同数据的解释正在改变，我们对其进行处理，我们如何与/进行交互使用它.
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屋！
