I've found some code
data Tree c a = Node String [Tree c a]
| NodeWithCleanup c [Tree c a]
| Leaf a
And I don't understand why it's necessary to add [Tree c a]. I don't know this syntax, can you explain it to me ?
4 Answers
The list type []
In Haskell lists (which are conceptually linked list) are a type []. A list can contain only one type of elements (so a list can not contain Int and Strings at the same time).
In case a list thus contains out of elements of type a, then we denote this as [a]. For example a list of Ints is denoted as [Int].
Note: this syntax is actually syntactical sugar. If you write
[a], behind the curtains you have actually written[] a.
Types (with type parameters)
In the code fragment you quote, the programmer defines a type Tree, and the type has two type parameters c (the type of the "cleanup") and a (the type of the "leaves"). So that means that a type Tree c a is a type for which c are the cleanup types and a are the leaf types.
If we thus want to construct a list of such Trees, we write [] (Tree c a), or more convenient [Tree c a].
Data constructors (with parameters)
The programmer has defined three data constructors. Data constructors can be seen as labels you attach to objects, and they bind "parameters" together. The number of parameters a data constructor has can differ, as well as the types.
In your code fragment there are three data constructors:
Nodea data constructor that takes two parameters: aStringand a list ofTree c as (its children);NodeWithCleanupa dataconstructor with again two parameters: ac(the cleanup) and a list ofTree c as (its children); andLeafa data constructor with a single parameter: the data it stores (of typea).
answered May 18, 2018 at 16:02
willeM_ Van Onsem
482k33 gold badges483 silver badges624 bronze badges
1 Comment
nam
this is really awesome! I get 4 quality answer for 20 minutes! This iswhy learning haskell a wonderful experience!
Like most “syntax” in Haskell these [] aren't really special syntax at all†. Constructor declarations simply list the types that are going to be contained. It might become clearer if you add record labels: (I'll diregard the “cleanup” part here)
data Tree a
= Node { nodeCaption :: String
, subtrees :: [Tree c a] }
| Leaf { leafContent :: a }
This is basically like two Python classes:
class TreeNode:
def __init__(self, caption, subs):
self.nodeCaption = caption
self.subtrees = subs
class TreeLeaf:
def __init__(self, content):
self.leafContent = content
...intended to be built like
TreeNode("foo", [TreeNode("bar1", TreeLeaf(1)), TreeNode("bar2", TreeLeaf(2))])
In the Haskell implementation, you just write
Node "foo" [Node "bar1" (Leaf 1), Node "bar2" (Leaf2)]
for that.
†Square brackets are special syntax in the sense that they are reserved for lists, but the do this the same way no matter if you write them in a function's type signature or in a data declaration.
Comments
When defining a value constructor K, the notation K T1 T2 .. Tn denotes that K is a constructor function taking n values, the first one being of type T1, and so on.
In Node String [Tree c a], we can see that Node takes two arguments. The first is a string (String). The second one is a list of trees ([Tree c a]). Hence, a node comprises both a string and a list of subtrees.
Instead, NodeWithCleanup c [Tree c a] means that a node-with-cleanup comprises a value of type c and a list of subtrees.
Leaf a means that leafs contain a single value of type a.
Comments
It's not a matter of syntax; it's a matter of semantics. A Leaf value just wraps a value of type a. The other two constructors wrap lists of Tree values, making this a recursive data structure. A Tree c a is either a leaf node (e.g. Leaf 3) or an interior node with an arbitrary number of subtrees as children (e.g. Node "foo" [Leaf 1, Leaf 3, (Node "bar" []]).
Leafcase do not has such[Tree c a].