Haskell函数寻求解释

Question

data BTree a = Empty | Node (BTree a) a (BTree a) -- This is a node-labelled binary tree

有人可以解释一下下面的Haskell函数吗？

1. labels :: BTree a -> [a]

   labels Empty = []
   labels (Node left label right) = labels left ++ [label] ++ labels right
   

2. reflect :: BTree a -> BTree a

   reflect Empty = Empty
   reflect (Node left label right) = Node (reflect left) label (reflect right)
   

Answer 1

第一:一些格式化.这就是通常在Haskell中格式化此代码的方式:

data BTree a = Empty 
             | Node (BTree a) a (BTree a)

labels :: BTree a -> [a]
labels Empty                   = [] 
labels (Node left label right) = labels left ++ [label] ++ labels right

reflect :: BTree a -> BTree a
reflect Empty                   = Empty 
reflect (Node left label right) = Node (reflect left) label (reflect right)

(提示:如果您将代码缩进4个空格,它将显示正确的语法突出显示).现在让我们来看看:

data BTree a = Empty 
             | Node (BTree a) a (BTree a)

定义新的"参数化"数据类型.它被称为参数,因为small a是一个类型参数.这意味着,a可以通过任何其他类型的替代,例如Int,Double,String,或任何.想想C++中的模板或Java中的泛型.Empty并被Node称为数据类型的构造函数.一个BTree a可以是Empty或(这就是|象征)包含Node其中包含BTree a一个a和另一个BTree a.该定义是递归的,因为datatype(BTree a)显示在它自己的定义中.

labels :: BTree a -> [a]
labels Empty                   = [] 
labels (Node left label right) = labels left ++ [label] ++ labels right

labels收集树中包含的所有值.第一行是类型声明:它采用带有anodes(BTree a)的二叉树并将其映射到as([a])列表.只有这种类型已经让你很好地了解可能发生的事情.

接下来的两行是所谓的模式匹配.这些与case其他语言中的语句类似:您区分不同的可能性,然后选择适当的情况(尽管它们更强大).您应该注意它们如何与具有的两个构造函数完全对应BTree a.如果我们在一个Empty节点,那么我们只返回一个空列表([]).否则,我们会落空到下一行,有一个Node必须有BTree a一个a和BTree a我们结合left,label和right.我们可能已经调用left,label而right无论我们想要的,但这些都是直观.

现在,left和right有型又BTree a使我们可以称之为labels双方并期望他们返回列表aS,即[a].因此标签也是递归的,因为它在其定义中调用自身.这是一种非常强大的技术,在Haskell中经常使用.labels然后连接它得到的列表labels left,一个只包含当前标签([label])然后它包含一个labels right.因此,我们可以有效地得出结论,它将左子树中的标签与当前标签和右子树中的标签连接起来,并将其全部放入列表中.

reflect :: BTree a -> BTree a
reflect Empty                   = Empty 
reflect (Node left label right) = Node (reflect left) label (reflect right)

labels除了它返回标签树而不是列表之外,其工作方式几乎相同.如此有效,这没有任何作用,它有点昂贵的身份功能.但它是一个更强大的模板.例如,您可以很容易地将另一个函数传递给reflect它并将其应用于每个元素.