时间戳

首页 > 解决方案 > 计算树 Haskell 中的节点数

haskell - 计算树 Haskell 中的节点数

问题描述

我是 Haskell 的新手，对一些语法片段（来自 C/C++）仍然有些困惑。

我有这个 Tree 数据类型（如下）和 t2 的构造函数

data Tree a b = Leaf a                                                          
              | Node b (Tree a b) (Tree a b)                                    
     deriving (Eq, Show)

 t2 :: Tree Bool Int                                                             
 t2 = Node 17 (Node 2 (Leaf True)                                                
                      (Node 7 (Leaf False)                                       
                              (Leaf False)))                                     
              (Leaf True)

我需要编写一个函数来计算树的节点

 sizeTree :: Tree a b -> Int

我很困惑为什么 sizeTree 会为函数传入“a”和“b”。是因为“a”有一个叶子，“b”有一个节点吗？我知道这需要递归调用，但我应该从哪里开始？

标签： haskell

解决方案

一些评论已经解决了您对类型签名的困惑，但我将尝试另一种方式来查看，比评论允许的更详细。

我们可以比较这个类型签名：

sizeTree :: Tree a b -> Int

与列表中的函数一样，说length函数：

length :: [a] -> Int

这个函数不“接受一个a”作为参数，它接受一个[a]，它代表一个列表，其元素是 type a。关键是它a 可以代表任何类型——事实上，将它显式写为是合法的forall a. [a] -> Int，这清楚地表明该函数适用于any列表类型。也就是说，一个length函数可以应用于 Ints 列表，或 Chars 列表（即字符串），或 aDouble和Integers 列表对列表的列表 - 希望您明白这一点。您可能认为这是理所当然的，您可以调用length [1,2,3]并length "hello"让它们都工作 - 但是，鉴于 Haskell 的强类型系统，这仅适用于多态类型。

完全相同Tree。这实际上是一个“类型族”，就像列表一样——它本身不是一个类型，没有 type 的值Tree。但是有类型的值Tree Int Charor Tree String (Int, Double)，以及任何你能想到的使用两个“具体类型”来代表 and 的a东西b。sizeTree :: Tree a b -> Int通过显式声明一个函数sizeTree :: forall a. forall b. Tree a b -> Int，您可以确保它适用于这些无限多不同的具体类型中的任何一个。

至于编写函数本身，它又类似于列表。列表类型虽然是 Haskell 内置的，但本质上有两个构造函数，一个用于空列表，另一个接受元素和现有列表（您可以自己定义等效类型data List a = Null | Cons a (List a)- 这意味着您可以在这两个构造函数上进行模式匹配， 去做：

length Null = 0
length (Cons _ l) = 1 + length l

或者，使用 Haskell 原生列表类型的内置“语法糖”：

length [] = 0
length (_:l) = 1 + length l

（如果您对 感到困惑_，它代表适当类型的任何值，这意味着在这种情况下我们不关心它的值，如果您愿意，我可以给它起任何名字，x比如说这将意味着完全相同的事情。）

希望这是足够的背景知识，可以帮助您了解正在发生的事情，并填写@Rusi 给您的开始 - 因为这是您Tree a b类型的两个构造函数，所以您需要在这两个构造函数上定义函数。进一步提示：Node构造函数将涉及对 的递归调用sizeTree，就像定义的第二行length也使用递归调用一样。

任何进一步的问题，请随时提问。

推荐阅读