如何在搜索树上定义地图和折叠？

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

您希望地图将函数应用于树所承载的任何标签.这意味着使用作为转换函数给出的函数将任何出现a更改为出现b.

要做到这一点,你需要弄清楚如何处理每个可能的构造函数Stree.现在,Null很容易 - 它a首先不依赖于它.Trickier是怎么做的Fork.在Fork,有一个a,另外两个Stree坐在那里,所以你需要采取a -> b和采取的功能Stree a -> Stree b.对于前者,调用mapStree为您提供了一个函数,对于后者,它mapStree f具有您需要的调用签名(通过部分应用程序!).

因为foldStree,你有一些累积类型b和你的标签类型a,以及一个累积函数,它接受两个类型b的值和一个类型的值,a并产生一个b.这是有帮助的,至少是因为累积函数反映Fork了树中任何给定的内容:通过递归,您可以假设您具有左右两侧的结果Stree,并且仅保留将它们与a您具有的值相结合在中间给出一个新b值来递交递归.该b参数foldStree为您提供足够的标准值,通过获取每个叶子的值来启动整个事件.

因此,您foldStree还需要在可能的构造函数上定义:为Null值选择参数,然后对于Fork值,它需要Stree在将所有内容与参数组合函数组合之前递归到两个值中.

请在评论中澄清这是否足以帮助您解决问题:我(以及此处的许多其他人)可以澄清,但希望您学会如何做而不是仅仅提供代码.