Standard definition of list

Question

I have a problem with definition of list. Normally is list defined as data [a] = [] | a : [a] but if I write something like this on my code concrete I will to define data T a = N | a -> (T a) the interpreter give me an error:

Malformed head of type or class declaration

Do you know what's wrong? .

Answer 1

It looks like your problem is that you tried to use -> as an infix constructor like : (In order to build a list using a -> b -> N syntax). This isn't allowed because custom infix constructors in Haskell must begin with the : character.

The reason for your strange error message is because -> in Haskell is reserved for function types, as Jeff's answer explains

Try this instead:

-- Create a right-associative infix constructor.
data T a = N | a :-> (T a)
infixr :->

mylist :: T Int
mylist = 10 :-> 17 :-> N

--If we hadn't made the operator right associative,
-- we would need to use explicit parenthesis here
myotherlist :: T Int
myotherlist = 10 :-> (17 :-> N)

-- Example function
isempty :: T a -> Bool
isempty N         = True
isempty (_ :-> _) = False

Answer 2

a -> T a would mean that a is a function that returns something of T a so I think that's the bit that's wrong. Try something like this.

data T a = N | R a (T a)

N is the empty list (equivalent of []) value and R is the value constructor (equivalent to :)

On the right hand side you need some way of carrying the a value around. You can now right lists like.

> N -- The empty List
> R 5 N -- a list with a single element and then the end
> R 7 (R 6 (R 5 N)) -- the list 7, 6, 5