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

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 :: (Ord a) => (b -> a -> b -> b) -> b -> Stree a -> b

我不完全明白发生了什么,也不知道如何做到这一点。

最佳答案

您希望您的 map 将一个函数应用于您的树携带的任何标签。这意味着任何 a 的出现都将更改为 b 的出现,使用作为转换函数给出的函数。

为此,您需要弄清楚如何处理 Stree 的每个可能的构造函数。现在,Null 很简单——它首先不依赖于 a。棘手的是如何处理 Fork 。在 Fork 中,有一个 a 和另外两个 Stree ,因此您需要使用 a -> bStree a -> Stree b 的函数。对于前者,mapStree 的调用为您提供了一个函数,而对于后者,mapStree f 具有您需要的调用签名(通过部分应用!)。

对于 foldStree ,您有一些累积类型 b 和标签类型 a ,以及一个累积函数,该函数采用 b 类型的两个值和 a 类型的值并生成 b 。这很有帮助,尤其是因为该累积函数反射(reflect)了您在树中任何给定 Fork 处可能拥有的内容:通过递归,您可以假设您拥有左右 Stree 的结果,并且只需要将它们与 a 结合起来中间的值可以提供一个新的 b 值来执行递归。 bfoldStree 参数为您提供了足够的标准值,通过获取每个叶子的值来开始整个事情。

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

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

关于search - 如何在搜索树上定义 map 和折叠?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/3982968/

10-11 23:03
查看更多