Haskell: Couldn't match type?

Question

One last question regarding type matching (for the time being, at least, lol).

In the following takeS formula right at the bottom of my code, I want to output a specific number of elements in a Snoc list defined as follows:

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

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

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

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

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

reverseS :: ListS a -> ListS a
reverseS NilS = NilS
reverseS l = (Snoc (reverseS(tailS(l))) (headS l))

takeS :: Int -> ListS a -> ListS a
takeS 0 _    = NilS
takeS _ NilS = error "Empty List"
takeS n l    = if n >= len(l) then 
               takeAux len(l) reverseS(l) else takeAux n reverseS(l) where
                   takeAux 0 l = l
                   takeAux n l = (Snoc (takeAux (n-1) initS(l)) (lastS l))

When I try to compile, I get the following error:

C:\Users\Google Drive\Ejercicio01.hs:31:20: error:
    * Couldn't match type `ListS a4' with `ListS a3 -> ListS a3'
      Expected type: t -> (ListS a3 -> ListS a3) -> ListS a4 -> ListS a4
        Actual type: t -> ListS a4 -> ListS a4
    * In an equation for `takeS':
          takeS n l
            = if n >= len (l) then
                  takeAux len (l) reverseS (l)
              else
                  takeAux n reverseS (l)
            where
                takeAux 0 l = l
                takeAux n l = (Snoc (takeAux (n - 1) initS (l)) (lastS l))
    * Relevant bindings include
        takeAux :: t -> (ListS a3 -> ListS a3) -> ListS a4 -> ListS a4
          (bound at C:\Users\Google Drive\Ejercicio01.hs:31:20)
   |
97 |                    takeAux 0 l = l
   |                    ^^^^^^^^^^^^^^^^...
Failed, no modules loaded.

As I see it, I'm trying to output the same type of list, but Haskell says I am creating a different type when calling the auxiliary function. Is that correct? It can get a bit confusing when dealing with these kind of errors at the beginning, so, besides helping me out by pointing at what the problem is, I would like to know if there's a repository or guide to understand better the intricacies of Haskell.

Thank you!

An important observation in your error message: len(l) doesn't parse to a function call like in most other languages, but as two separate expressions len and (l). Writing (len l) (and, correspondingly, (reverseS l)) might be more correct and confuse the compiler less. — David Maze
takeAux len(l) reverseS(l) is calling takeAux with four arguments (the parentheses are redundant). — chi
Oh wow, I totally missed that! Thank you for the observation. You are correct, I am calling length when, in fact, in my code I also implemented a lenS function which works with Lists of the type Snoc. I really appreciate all of your corrections, it's helping me a big deal to improve. — Arthur Champs

bipll bipll · Accepted Answer · 2018-08-18T20:58:27

You're not writing curried applications right. Should be something like

takeS n l = if n >= (len l) then 
           takeAux (len l) (reverseS l) else takeAux n (reverseS l) where
               takeAux 0 l = l
               takeAux n l = (Snoc (takeAux (n-1) (initS l)) (lastS l))

Parentheses are used for grouping in Haskell, never as an operator (tuple construction put aside.)

As a side note, there are few inconsistencies in your code:

Are there any name clashes with standard Prelude in your code? len is a standard function that measures the length of lists.
reverse is quadratic. Why do you need headS and tailS here, when you've got init and last in no time (i.e. in O(1))?
There's inconsistency in takeS contract: takeS 2 NilS is an error yet takeS 3 (Snoc NilS 42) returns a tsil. You don't really need length in the last match.

Haskell: Couldn't match type?

2 Answers