Right rotate of tree in Haskell: how is it work?

Question

I don't know haskell syntax, but I know some FP concepts (like algebraic data types, pattern matching, higher-order functions ect).

Can someone explain please, what does this code mean:

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)

As I understand, first line is something like Tree-type declaration (but I don't understand it exactly). Second line includes pattern matching (I don't understand as well why do we need to use pattern matching here). And third line does something absolutely unreadable for non-haskell developer. I've found definition of Fork as fork (f,g) x = (f x, g x) but I can't move further anymore.

Answer 1

I think you misunderstand Fork. It is not a function, but a constructor for type Tree. It is essentially a node in the Tree data structure... Each node in Tree is either a Leaf (with a value) or a Fork (with a value and two sub-nodes).

Pattern matching is used to transform the structure. My ASCII art is not good enough to give you a drawing, but it sort-of moves 'left nodes' up and 'right nodes' down.

Note: I say you may be misunderstanding Fork, because fork (f,g) x = (f x, g x) is something completely different. It is a higher order function in this case and has nothing to do with your Tree structure.

Hope that helps :), Carl

Answer 2

First of all the data type definition should not contain question marks, but normal letters:

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

It defines a type Tree that contains elements of some not further specified type a. The tree is either a Leaf, containing an element of type a, or it is a Fork, containing also an element of type a and two subtrees. The subtrees are Tree structures that contain elements of type a.

Important to note is that Haskell uses parenthesis purely for grouping, like in 2 * (2+3), not to specify calling functions. To call functions, the parameters are just written after the function name, separated with spaces, like in sin 30 or compare "abc" "abd".

In the case statement, the part to the left of -> is a pattern match, the part to the right is the functions result in case the tree actually had the form specified on the left. The pattern Fork q (Fork p a b) c matches if the tree is a Fork (that's the Fork from the data type definition) and the first subtree of it is another Fork. The lowercase letters are all just variables, capturing the different parts of the tree structure matched. So p would be the element contained in the subtree, a would be the subtrees first branch and b the second one.

The right side of the ->, Fork p a (Fork q b c), now builds a new tree from these parts matched in the pattern match. The lower case variables are all the tree parts matched on the left, and the Forks are the constructors from the data type definition. It build a tree that is a Fork and has a second subtree that is also a Fork (the part in parenthesis). The remaining pieces of this tree are just the parts of the tree that has been "dissolved" on the left side.