在Haskell树上遍历打印

我有以下玩具哈希克尔代码为二叉搜索树。函数preorderV是用遍历每个元素的函数遍历树的。它对正常功能正常工作。但是，如果我应用函数“打印”，我得到编译错误。如何使用preorderV进行与IO工作相关的功能？在Haskell树上遍历打印

感谢

代码：

data BSTree a = EmptyTree | Node a (BSTree a) (BSTree a) deriving (Show) 
data Mode = IN | POST | PRE 

singleNode :: a -> BSTree a 
singleNode x = Node x EmptyTree EmptyTree 

bstInsert :: (Ord a) => a -> BSTree a -> BSTree a 
bstInsert x EmptyTree = singleNode x 
bstInsert x (Node a left right) 
      | x == a = Node a left right 
      | x < a = Node a (bstInsert x left) right 
      | x > a = Node a left (bstInsert x right) 

buildTree :: String -> BSTree String 
buildTree = foldr bstInsert EmptyTree . words  

preorderV :: (a->b) -> BSTree a -> BSTree b 
preorderV f EmptyTree = EmptyTree 
preorderV f (Node x left right) = Node (f x) (preorderV f left) (preorderV f right)

错误：

Couldn't match type ‘BSTree’ with ‘IO’ 
Expected type: IO (IO()) 
    Actual type: BSTree (IO()) 
In a stmt of a 'do' block: preorderV print $ buildTree content

来源

2014-10-06 Yan Zhu

你能张贴包含'print'的代码？我很好奇它为什么期望类型'IO（IO（））'而不是'IO（）'（它会给出一个错误，但我不希望在这里看到IO（IO（））' ）。我怀疑这是代码的另一个可能独立的问题。 – 2014-10-06 04:28:27

打印是前奏的功能 – 2014-10-07 01:10:16

我知道，我的意思是你没有在你的文章中围绕这行代码的代码：'preorderV print $ buildTree content' – 2014-10-07 01:59:10

preorderV print $ buildTree content的类型是BSTree (IO())，也就是说，您正在创建IO计算的二叉树 - 您自己没有IO计算。

做什么，我想你想你需要创建一个preorderV一元版本，它具有以下类型：

preorderVM :: (a -> IO()) -> BSTree a -> IO() 
preorderVM f EmptyTree = ... -- what do you want to do here? 
preorderVM f (Node x left right) = do 
    f x 
    preorderVM f left 
    preorderVM f right

来源

2014-10-06 04:31:03 ErikR

作为一个注释，该类型可以推广到适用于任何'Applicative '，而不仅仅是'IO'。 – 2014-10-06 04:32:08

'preorderVM'基本上是'Data.Traversable.traverse'或'Data.Traversable.mapM'，而GHC可以派生'Traversable'，所以你甚至不必自己写这个。 – user2407038 2014-10-06 15:25:36

@ user2407038 - 确实如此，知道这一点很有用。 OTOH我认为在引入泛化之前，初学者可以准确地看到究竟发生了什么。此外，这种方法向您展示了如何编写'postorderVM'和'inorderVM'。 – ErikR 2014-10-06 17:22:01

你的代码的工作到目前为止，但你有一个BSTree (IO())回来，当你使用这个do块内（main最可能）你会得到错误。

你现在能做的就是倍在树得到的动作后面是什么，那么你可以使用sequence或类似使用每这些行动的一前一后的东西：

foldT :: (a -> s -> s) -> s -> BSTree a -> s 
foldT _ s EmptyTree = s 
foldT f s (Node a left right) = 
    let s' = foldT f s left 
     s'' = f a s' 
    in foldT f s'' right 

main :: IO() 
main = do 
    let doPrint = preorderV print $ buildTree "C A B D E" 
     folded = foldT (:) [] doPrint 
    sequence_ . reverse $ folded

这将打印

λ> :main 
"A" 
"B" 
"C" 
"D" 
"E"

BTW：您preorderV通常被称为map;）

来源

2014-10-06 04:29:10 Carsten

在Haskell树上遍历打印

回答

相关问题