0

我在八月的 Haskell 中有重复，所以我正在尝试练习我的 Haskell。其中一个问题是：

“通过将列表的元素存储到二叉树中，然后遍历二叉树，以便按照右孩子、父母和左孩子的顺序访问子树的节点，来执行列表的反向猴子拼图排序。写一个Haskell中的反向猴子拼图排序“

这个问题让我很困惑。我知道我必须编写一个函数去 xr Node xl。但这是否必须从遍历的树中输出一个列表？或者我用列表重新填充二叉树还是什么？另外，我是从最右边的元素开始，然后到那个父元素然后向左走，还是从树顶部的第一个根节点开始，然后走那条路？

另外我将如何编写它，Haskell 是我的弱点之一。感谢您对此的任何帮助！

这是我的代码

module Data.BTree where

data Tree a = Tip | Node a (Tree a) (Tree a) deriving (Show,Eq)

leaf x = Node x Tip Tip

t1 = Node 10 Tip Tip
t2 = Node 17 (Node 12 (Node 5 Tip(leaf 8)) (leaf 15))
         (Node 115
                (Node 32 (leaf 30) (Node 46 Tip (leaf 57)))
                (leaf 163))
t3 = Node 172 (Node 143 (Node 92 (Node 76 (leaf 32) (leaf 45)) (Node 58 (leaf 39) (leaf 52))) (Node 107 (Node 92 (leaf 64) (leaf 35)) (Node 86 (leaf 69) (leaf 70))))
          (Node 155 (Node 127 (leaf 83) (leaf 97)) (Node 138 (leaf 107) (leaf 91)))
4

1 回答 1

2

你可以写

data Tree a = Empty | Tree (Tree a) a (Tree a)

ins :: Ord a => Tree a -> a -> Tree a
ins Empty x = Tree Empty x Empty
ins (Tree l y r) x = if x < y then Tree (ins l x) y r else Tree l y (ins r x)

fromList :: Ord a => [a] -> Tree a
fromList = foldl ins Empty -- <<< FOLDABLE

toList :: Ord a => Tree a -> [a]
toList Empty = []
toList (Tree l x r) = (toList l) ++ [x] ++ (toList r) -- <<< MONOID
                                                      -- (change order if you wish)

sort :: Ord a => [a] -> [a]
sort = toList . fromList

直接解决您的问题。

一般来说，使用更抽象的结构是有用的，比如monoid, foldable, ... 你可以（必须）阅读Learn You Haskell for Great Good！

:)

例子

*Main> sort [6, 3, 7, 8, 3, 6]
[3,3,6,6,7,8]

正如所评论的（在代码中），一种更通用的方法是将一些有用的结构定义到Tree:Foldable和Monoid其他结构中。

假设我们实现了两个结构：

import Data.Foldable
import Data.Monoid

data Tree a = Empty | Tree (Tree a) a (Tree a) deriving Show

-- Shortcut
leaf :: Ord a => a -> Tree a
leaf x = Tree Empty x Empty

instance Foldable Tree where
    foldMap f Empty = mempty
    foldMap f (Tree l k r) = foldMap f l `mappend` f k `mappend` foldMap f r

-- WARNING: in that monoid only traverse result (ordered list) is invariant!
instance Ord a => Monoid (Tree a) where
    mempty = Empty
    mappend Empty tree = tree
    mappend tree Empty = tree
    mappend (Tree l x r) tree = ins (l `mappend` r `mappend` tree) x
        where ins Empty x = leaf x
              ins (Tree l y r) x = if x < y then Tree (ins l x) y r else Tree l y (ins r x)

这在 Haskell 中很常见。

现在，您的问题（sort使用加载/卸载树在列表上定义）很简单：

sort :: Ord a => [a] -> [a]
sort = foldMap return . foldMap leaf

@m0nhawk、@tel 和 @petr-pudlak 在这个问题中详细介绍了一种更通用的方式（结构）

于 2013-07-24T12:29:17.303 回答