Haskell Recursive Type

Question

I am attempting to create a function in Haskell returning the `Resp` type illustrated below in a strange mix between BNF and Haskell types. ``` elem ::= String | (String, String, Resp) Resp ::= [elem] ``` My question is (a) how to define this type in Haskell, and (b) if there is a way of doing so without being forced to use custom constructors, e.g., `Node`, rather using only tuples and arrays.

Accepted Answer

Part 1:

```
data Elem = El String | Node String String Resp
type Resp = [Elem]
```

Part 2: Well... kinda. The unsatisfying answer is: You shouldn't want to because doing so is less type safe. The more direct answer is `Elem` needs it's own constructor but `Resp` is easily defined as a type synonym as above. However, I would recommend

```
newtype Resp = Resp { getElems :: [Elem] }
```

so that you can't mix up some random list of `Elem`s with a `Resp`. This also gives you the function `getElems` so you don't have to do as much pattern matching on a single constructor. The `newtype` basically let's Haskell know that it should get rid of the overhead of the constructor during runtime so there's no extra indirection which is nice.

Haskell Recursive Type

Solution

Problem