defining a type for a nonempty list

2
votes

I'm trying to get used to defining recursive types in Haskell. As a simple exercise, I figured that defining a nonempty list data type would be easy (and potentially useful).

Here is my attempt:

data NonemptyList a = Singleton a | Cons (Singleton a) (NonemptyList a)

which results in the compile error:

Not in scope: type constructor or class `Singleton'
Failed, modules loaded: none.

The following code compiles but doesn't sit well with me. I can't exactly explain why not. 

data NonemptyList a = Singleton a | Cons  a (NonemptyList a)

Can anyone clarify this for me? Any comments are welcome.

Thanks

dan

2
haskellrecursiontypes
In your case, Singleton is a data constructor — you use these to define values. When defining types, you use type constructors. These two are different concepts and you can't mix them. All I can say is that the second option (the one that works) is perfectly fine, I don't know why you don't like it. - Paul Manta
The fields of a constructor are types, not constructors. Notice how the second field of Cons is NonemptyList a; NonemptyList a is a type. - Gabriella Gonzalez
Thanks for the quick and clear replies. I think I understand my mistake now. In the following code, Singleton is a data constructor and SingletonType & NonemptyListType are type constructors. This code compiles. data SingletonType a = Singleton a data NonemptyListType a = SingletonType a | Cons (SingletonType a) (NonemptyListType a) - sitiposit

2 Answers

9
votes

This is because you used Singleton (a data constructor) in a place where a type constructor is expected. In this example, Singleton and Cons are data constructors and Nonemptylist is a type constructor. It is easy to confuse these two concepts, because it is common to define a data constructor and a type constructor with the same name, e.g. data Foo a = Foo a.

In this case, data NonemptyList a = Singleton a | Cons a (NonemptyList a) probably is the correct code to use.

4
votes

As a side note, a simpler way to define a non-empty list is:

data NonEmpty a = NonEmpty { head :: a, tail :: [a] }

The most popular package for non-empty lists is the semigroups package, which has something similar to the above definition in the Data.List.NonEmpty module.