折二叉树 [英] Fold for Binary Tree

问题描述

我必须实现实例化类型类的Binary Tree:

I have to make an implementation of a Binary Tree instantiate a typeclass:

class Set s where
    add :: (Eq a) => a -> s a -> s a
    remove :: (Eq a) => a -> s a -> s a
    exists :: (Eq a) => a -> s a -> Bool
    fold :: (a -> b -> b) -> s a -> b -> b

data BTree k v = Empty | Node k v (BTree k v) (BTree k v) deriving (Show)

一切顺利，直到我不得不为二叉树实现折叠.我遇到的问题是我真的不知道如何使用这样的签名来保存函数的类型声明:(a -> b -> b).我已经实现了折叠，但是我的匿名函数的函数签名具有1个累加器和2个值:

All went well until I had to implement a fold for a binary tree. The issue I'm having is that I don't really know how to keep the type declaration of my function with a signature like this: (a -> b -> b) . I've implemented a fold but the function signature for my anonymous function has 1 accumulator and 2 values:

foldBST :: (v -> a -> a -> a) -> a -> (BTree k v) -> a
foldBST _ startval Empty = startval
foldBST f startval (Node k v left right) = f v (foldBST f startval left) (foldBST f startval right)

如何让匿名函数具有类似于(a -> b -> b)的签名?除了以递归方式调用左右子节点上的fold之外，我无法采用其他任何方式，但这将返回类型为a的值.

How can I have the anonymous function have a signature like (a -> b -> b) ? I can' thing of any other way than calling the fold recursively on the left and right child, but this will return a value of type a.

我该怎么做?

推荐答案

您可以引入一个中间结果:

You can introduce an intermediate result:

foldBST f startval (Node k v left right) = f v i
  where i = foldBST f j left
        j = foldBST f startval right

如果您不喜欢中间结果，则可以内联它们.

and if you don't like intermediate results, you can just inline them.

这篇关于折二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！