Haskell newbie: Return type mismatch

Question

I ran into a roadblock trying to figure out why I can't compile the following code. I'm defining several functions to work with a "snoc" list. the headS works properly but in the tailS function, I cannot return a NilS and I was wondering why. I know this might be a very basic issue but I have already tried googling yet I got more confused. Hope you can help me understand what am I missing. Here's my code:

data ListS a = NilS
          |Snoc (ListS a) a deriving Show

headS :: ListS a -> a
headS NilS          = error "Empty List"
headS (Snoc NilS a) = a
headS (Snoc a b)    = headS a

tailS :: ListS a -> a
tailS NilS          = error "Empty List"
tailS (Snoc NilS a) = NilS

I get the following error:

* Couldn't match expected type `a' with actual type `ListS a0'
  `a' is a rigid type variable bound by
    the type signature for:
      tailS :: forall a. ListS a -> a
    at Ejercicio01.hs:9:1-21
* In the expression: NilS
  In an equation for `tailS': tailS (Snoc NilS a) = NilS
* Relevant bindings include
    a :: a (bound at Ejercicio01.hs:11:18)
    tailS :: ListS a -> a (bound at Ejercicio01.hs:10:1)
   |
11 | tailS (Snoc NilS a) = NilS
   |                       ^^^^
Failed, no modules loaded.

Thanks in advance for your time,

Answer 1

Well the compiler is correct. The type signature of your function is:

tailS :: ListS a -> a

So the output type should be an a. But here you write as return value NilS. Now NilS is a data constructor of the ListS a type. So the two do not match: your signature says that you will return an element of your "list" type, but in the function definition, you return a list (that might actually wrap elements of another type).

What you probably want is to return the a element, and not an NilS, so:

tailS :: ListS a -> a
tailS NilS = error "Empty List"
tailS (Snoc NilS a) = a

But there is still another problem. If we compile it with -Wincomplete-patterns, then the compiler will tell that there is a pattern that is not covered: the Snoc (Snoc _ _) _ pattern. In your last line you write tailS (Snoc NilS a), so you restrict it to the first item of the Snoc being a NilS. This is not necessary, regardless of what the "prefix list" is, the tail is always the second parameter, so we can fix this with:

tailS :: ListS a -> a
tailS NilS = error "Empty List"
tailS (Snoc _ a) = a