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

我的影片定义为搜索树：如何在搜索树上定义贴图和折叠？

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

我不完全了解发生了什么，不知道如何做到这一点。

来源

2010-10-20 fotg

（题外话）。 GHC可以自动派生Functor和Foldable来定义上述两个函数（假设'Ord a =>'约束不存在）。 – kennytm 2010-10-21 07:02:01

目前还不清楚Ord的作用是什么。我认为这棵树是由Ord实例排序的，从左到右。在这种情况下，是否允许'mapStree'假定它的函数是单调的（即保留顺序）还是mapStree需要重新排序？ – mokus 2010-10-21 13:29:01

教授谈论的大部分内容都不清楚，我甚至不确定他是否知道Ord自己做了什么，因为他无法解释它。 – fotg 2010-11-01 21:00:31

您希望您的地图将功能应用于树中携带的任何标签。这意味着使用作为变换函数给出的函数，将a的任何出现更改为b。

要做到这一点，你需要弄清楚如何处理Stree的每个可能的构造函数。现在，Null很容易 - 它首先不会依赖于a。 Trickier是如何处理Fork。在Fork中，有一个a，和另外两个Stree s，所以你需要的功能是a -> b并且需要Stree a -> Stree b。对于前者，mapStree的调用为您提供了一个功能，对于后者，mapStree f具有您需要的呼叫签名（通过部分应用！）。

为foldStree，你有一些积累型b和你labeltype a和累积函数，它b类型的两个值和a类型的值，并产生一个b。这很有帮助，因为这种积累函数反映了树中任何给定Fork的情况：通过递归，您可以假设您有来自左侧和右侧Stree的结果，并且只保留将这些结果与a值在中间给出一个新的b值来递归递归。 b参数foldStree为您提供了足够的标准值，以通过获取每个叶的值来开始整个事情。

因此，您foldStree也将需要对可能的构造函数定义：挑选出参数的Null值，然后为Fork值，它需要的一切都与参数组合结合之前递归到两个Stree值功能。

请在意见中澄清一下，这是否有助于您解决问题：我（以及其他许多人）可以澄清，但希望您能学会如何去做，而不是只交给您代码。

来源

2010-10-20 23:07:48

你在'mapStree f（Fork left x right）'上的第二次尝试看起来很不错：你会想把'mapStree f'应用于'left'和'right'，并且你想要'f'应用' x'。 – 2010-10-21 06:28:39

@ a.d。 'f（x）'在你尝试的时候没有做你认为的事情 - 它会把f和y作为连续的参数传递给Fork，这会导致类型错误。看起来你理解函数应用语法，因为你得到了（mapStree f xt）和（mapStree f yt），所以我猜这可能只是一个错字。 – mokus 2010-10-21 13:33:45

我强烈推荐this course第5讲。

来源

2010-10-21 19:47:28

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

回答

相关问题