How to use custom version of List: `data List a = Nil | Cons a (List a)`?

The parameters you pass to the len are not Lists. The end of a list has Nil, so lists are of the form Nil, Cons … Nil, Cons … (Cons … Nil), Cons … (Cons … (Cons … Nil)), etc. So eventually for each list, the end of the list is marked with Nil. Nil is the equivalent to [] for Haskell's [a] type.

Furthermore you can not pass len Cons 1 Nil for example, since then it will be interpreted as ((len Cons) 1) Nil. The parameter should be a list. By using parenthesis, you can write this as len (Cons 1 Nil).

For the given sample data, you thus can rewrite this to:

• len Cons 1 Cons 2 Cons 3 → len (Cons 1 (Cons 2 (Cons 3 Nil)))
• len 1 → len (Cons 1 Nil)
• len Cons → len Nil
• len (1) → len (Cons 1 Nil)
• len [1,2] → len (Cons 1 (Cons 2 Nil))
• len Cons [1] → len (Cons 1 Nil)
• len (1,2) → len (Cons 1 (Cons 2 Nil))
• len Cons (1,2) → len (Cons 1 (Cons 2 Nil))
• len Cons 1 2 → len (Cons 1 (Cons 2 Nil))
• len (Cons (1,2)) → len (Cons 1 (Cons 2 Nil))
• len (Cons 1 2) → len (Cons 1 (Cons 2 Nil))

You can also make use of the OverloadedLists [haskell-doc] extension to use list syntax instead. In that case, you need to implement the IsList type class:

{-# LANGUAGE TypeFamilies #-}

import GHC.Exts(IsList(..))

data List a = Nil | Cons a (List a)

instance IsList (List a) where
    type Item (List a) = a
    toList Nil = []
    toList (Cons x xs) = x : toList xs
    fromList [] = Nil
    fromList (x:xs) = Cons x (fromList xs)

If you then enable the OverloadedLists extension, you can write these as list literals:

{-# LANGUAGE OverloadedLists #-}

-- …

main = print (len [1,2])

You use a function exactly as it is defined:

len  Nil         = 0
len (Cons _x xs) = 1 + len xs

then,

list1 = Nil           -- matches the first pattern
list2 = Cons 2 list1  -- matches the second pattern
list3 = Cons 3 list2  -- matches the second pattern
list4 = Cons 4 list3  -- matches the second pattern

and so on and so forth.

Writing out such example data by hand we need to use parentheses to correctly group the sub-terms to recreate the valid term, as e.g.

list5 = Cons 5 list4
      = Cons 5 (Cons 4 list3)
      = Cons 5 (Cons 4 (Cons 3 list2))
      = ...
      = Cons 5 (Cons 4 (Cons 3 (Cons 2 Nil)))

All this without even having looked at the data type definition.

Of course anything can be used in place of 1, 2, etc., as long as they are all of the same type, e.g. the following is also a valid term:

list54 = Cons list5 (Cons list4 Nil)

Why? Because of the data type definition,

data List a = Nil           --  `Nil` constructs (is) a valid `List a` type term,
            |               -- OR,
              Cons          --  `Cons x xs` constructs (is) a valid `List a` type term,  IF 
                   a        --       `x` is a valid term of type `a`                  ,  AND
                  (List a)  --       `xs` is a valid term of type `List a`

Nil constructs (is) a valid List a type term, while Cons x xs constructs (is) a valid List a type term, if x is a valid term of type a and xs is a valid term of type List a, where a is one and the same.

So e.g. Cons 1 (Cons list2 Nil) is not a valid term according to the List a data type definition, even though the function len could seemingly handle it as well.