在Haskell中正确旋转树:它是如何工作的？

Question

我不知道haskell语法,但我知道一些FP概念(如代数数据类型,模式匹配,高阶函数等).

有人可以解释一下,这段代码意味着什么:

data Tree ? = Leaf ? | Fork ? (Tree ?) (Tree ?)

rotateR tree = case tree of
  Fork q (Fork p a b) c -> Fork p a (Fork q b c)

据我所知,第一行就像Tree-type声明(但我完全不明白).第二行包括模式匹配(我不明白为什么我们需要在这里使用模式匹配).第三行为非haskell开发人员做了一些绝对不可读的事情.我已经找到了Fork的定义,fork (f,g) x = (f x, g x)但我不能再继续前进了.

Answer 1

首先,数据类型定义不应包含问号,而应包含正常字母:

data Tree a = Leaf a | Fork a (Tree a) (Tree a)

它定义了一个Tree包含某些未进一步指定类型的元素的类型a.树是a Leaf,包含类型的元素a,或者是a Fork,还包含类型元素a和两个子树.子树是Tree包含类型元素的结构a.

需要注意的是,Haskell仅使用括号进行分组,例如2 * (2+3),不指定调用函数.要调用函数,参数只写在函数名后面,用空格分隔,如in sin 30或compare "abc" "abd".

在case语句中,左边的部分->是模式匹配,右边的部分是函数结果,以防树实际上具有左边指定的形式.Fork q (Fork p a b) c如果树是a Fork(Fork来自数据类型定义)并且它的第一个子树是另一个,则模式匹配Fork.小写字母都只是变量,捕获匹配的树结构的不同部分.那么p子树中包含的元素就是子a树第一个分支和b第二个分支.

的右侧->,Fork p a (Fork q b c)现在建立从这些部件在模式匹配相匹配的新树.小写变量是左边匹配的所有树部分,Forks是数据类型定义中的构造函数.它构建了一个树,它是一个Fork第二个子树,也是一个Fork(括号中的部分).这棵树的其余部分只是左侧"溶解"的树的部分.