search - 如何在搜索树上定义映射和折叠？

Question

我有一个定义为的搜索树:

data (Ord a) => Stree a = Null | Fork (Stree a) a (Stree a) deriving Show 

我必须定义两个函数，mapStree:

mapStree :: (Ord b, Ord a) => (a -> b) -> Stree a -> Stree b

和 foldStree:

foldStree :: (Ord a) => (b -> a -> b -> b) -> b -> Stree a -> b

我不完全明白发生了什么，也不知道该怎么做。

Answer 1

您希望您的 map 将函数应用到树携带的任何标签。这意味着任何 a 的出现将更改为 b 的事件，使用给定的函数作为转换函数。

为此，您需要弄清楚如何处理 Stree 的每个可能的构造函数.现在，Null很简单——它不依赖于 a首先。更棘手的是如何处理 Fork .在 Fork , 有一个 a , 还有两个 Stree它无处不在，所以你需要使用 a -> b 的函数那需要Stree a -> Stree b .对于前者，调用 mapStree给你一个函数，对于后者，mapStree f具有您需要的调用签名(通过部分应用程序!)。

对于 foldStree , 你有一些积累类型 b和你的标签类型 a , 和一个累加函数，它采用 b 类型的两个值和一个 a 类型的值并产生 b .这很有用，至少因为累积函数反射(reflect)了你在任何给定 Fork 可能拥有的东西。在树中:通过递归，你可以假设你从左和右都有结果 Stree , 剩下的就是将它们与 a 结合起来你在中间的值(value)给一个新的 b递归递归的值。 b参数 foldStree为您提供足够的标准值，通过获取每片叶子的值来启动整个过程。

因此，您的 foldStree还需要在可能的构造函数上定义:为 Null 挑选参数值，然后为 Fork值，它需要递归到Stree在使用参数组合函数组合所有内容之前的值。

请在评论中澄清这是否足以帮助您解决问题:我(和这里的许多其他人)可以澄清，但希望您学习如何去做，而不是仅仅交给您代码。