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.

Answer 1

You said that "the variety of keywords (data, type, newtype) has been confusing for me". Here's a quick primer on the data construction keywords in Haskell.

Data

The canonical way to create a new type is with the data keyword. A general type in Haskell is a union of product types, each of which is tagged with a constructor. For example, an Employee might be a line worker (with a name and a salary) or a manager (with a name, salary and a list of reports).

We use the String type to represent an employee's name, and the Int type to represent a salaray. A list of reports is just a list of Employees.

data Employee = Worker  String Int
              | Manager String Int [Employee]

Type

The type keyword is used to create type synonyms, i.e. alternate names for the same type. This is typically used to make the source more immediately understandable. For example, we could declare a type Name for employee names (which is really just a String) and Salary for salaries (which are just Ints), and Reports for a list of reports.

type Name    = String
type Salary  = Int
type Reports = [Employee]

data Employee = Worker  Name Salary
              | Manager Name Salary Reports

Newtype

The newtype keyword is similar to the type keyword, but it adds an extra dash of type safety. One problem with the previous block of code is that, although a worker is a combination of a Name and a Salary, there is nothing to stop you using any old String in the Name field (for example, an address). The compiler doesn't distinguish between Names and plain old Strings, which introduces a class of potential bugs.

With the newtype keyword we can make the compiler enforce that the only Strings that can be used in a Name field are the ones explicitly tagged as Names

newtype Name    = Name String
newtype Salary  = Salary Int
newtype Reports = Reports [Employee]

data Employee = Worker  Name Salary
              | Manager Name Salary Reports

Now if we tried to enter a String in the Name field without explicitly tagging it, we get a type error

>>> let kate = Worker (Name "Kate") (Salary 50000)     -- this is ok
>>> let fred = Worker "18 Tennyson Av." (Salary 40000) -- this will fail

<interactive>:10:19:
    Couldn't match expected type `Name' with actual type `[Char]'
    In the first argument of `Worker', namely `"18 Tennyson Av."'
    In the expression: Worker "18 Tennyson Av." (Salary 40000)
    In an equation for `fred':
        fred = Worker "18 Tennyson Av." (Salary 40000)

What's great about this is that because the compiler knows that a Name is really just a String, it optimizes away the extra constructor, so this is just as efficient as using a type declaration -- the extra type safety comes "for free". This requires an important restriction -- a newtype has exactly one constructor with exactly one value. Otherwise the compiler wouldn't know which constructor or value was the correct synonym!

One disadvantage of using a newtype declaration is that now a Salary is no longer just an Int, you can't directly add them together. For example

>>> let kate'sSalary = Salary 50000
>>> let fred'sSalary = Salary 40000
>>> kate'sSalary + fred'sSalary

<interactive>:14:14:
    No instance for (Num Salary)
      arising from a use of `+'
    Possible fix: add an instance declaration for (Num Salary)
    In the expression: kate'sSalary + fred'sSalary
    In an equation for `it': it = kate'sSalary + fred'sSalary

The somewhat complicated error message is telling you that a Salary isn't a numeric type, so you can't add them together (or at least, you haven't told the compiler how to add them together). One option would be to define a function that gets the underlying Int from the Salary

getSalary :: Salary -> Int
getSalary (Salary sal) = sal

but in fact Haskell will write these for you if you use record syntax when declaring your newtypes

data Salary = Salary { getSalary :: Int }

Now you can write

>>> getSalary kate'sSalary + getSalary fred'sSalary
90000