How to use this type: data List a = Nil | <<<Cons a (List a)

This is a book exercise (as usual for me) and I really don’t understand the type:

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

List a in Cons a (List a) looks like a data constructor but I don’t know how to use it. Nor do I know how to use the types methods.

The exercise gives the type and asks that you create instances for Functor, Applicative & Monad.

Here is the answer I found on Github:

data List a = Nil | Cons a (List a)
  deriving (Show, Eq)

append :: List a -> List a -> List a
append Nil ys         = ys
append (Cons x xs) ys = Cons x $ xs `append` ys

instance Functor List where
  fmap _ Nil         = Nil
  fmap f (Cons a as) = Cons (f a) (fmap f as)

instance Applicative List where
  pure a = Cons a Nil
  Nil <*> _ = Nil
  _ <*> Nil = Nil
  (Cons f fs) <*> as = fmap f as `append` (fs <*> as)

instance Monad List where
  return = pure
  Nil >>= _ = Nil
  (Cons a as) >>= f = f a `append` (as >>= f)

My attempts to make use of it

ghci> (Cons 5 [2,3]) >>= (+1)

<interactive>:7:9: error:
    • Couldn't match expected type: List (List b)
                  with actual type: [a0]
    • In the second argument of ‘Cons’, namely ‘[2, 3]’
      In the first argument of ‘(>>=)’, namely ‘(Cons 5 [2, 3])’
      In the expression: (Cons 5 [2, 3]) >>= (+ 1)
    • Relevant bindings include
        it :: List b (bound at <interactive>:7:1)

ghci> fmap (+1) (Cons 5 [3,4])

<interactive>:8:19: error:
    • Couldn't match expected type: List b
                  with actual type: [a0]
    • In the second argument of ‘Cons’, namely ‘[3, 4]’
      In the second argument of ‘fmap’, namely ‘(Cons 5 [3, 4])’
      In the expression: fmap (+ 1) (Cons 5 [3, 4])

ghci> fmap (+1) (Cons 5 List [3,4])

<interactive>:9:19: error:
    Data constructor not in scope: List :: List a1


>  (Cons 5 [2,3]) >>= (+1)
-- Error
> (Cons 5 (List [2,3])) >>= (+1)
```Error

But neither are conrrect usage.

I'm thinking of `List a` as a type that is only visible withoun `Cons`. Is that right/

What would be an example of using this type from GHCi?
1 Like

Hint: heed the compiler, you passed [2, 3] (which has a type [Int]) but it wants some data of type List.

What is the simplest thing of type List you can construct?

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

So this defines a “type” List a, and it has 2 data constructors: Nil and Cons. Nil is a nullary constructor, meaning that it stands alone, you don’t pass anything into it. You can have xs = Nil :: List Int. Cons is a constructor that takes 2 inputs, one of type a, and one of type List a. That’s where it gets interesting, because List there is referring back to the same type you’re defining in data List a = .... List then is called a “recursive type” because it references itself in its own definition. Sort of like you can have a recursive function that can reference itself:

fib 0 = 1
fib 1 = 1
fib x = fib (x - 1) + fib (x - 2) -- see how we refer to `fib` in our definition of `fib`

So List is not a data constructor at all. List a is a “type”, but if you want to construct a value, you have to use either Nil or Cons.

Now I think one of your hangups is that this exercise is defining a new List type, which is basically equivalent to the [] type in Prelude, but they’re completely separate. So you can’t take a [Int] and somehow get any kind of List Int out of it. So, considering that

  • a List Int can only be constructed using Cons & Nil (and no []s from Prelude like [2, 3])
  • List is recursive, so you need a value of type List a in order to create a List a using Cons

Can you figure out how to construct a List Int that would be equivalent to the Prelude [Int]: [5, 2, 3]?

Hint: When defining a recursive function, it can help to think through “what’s the simplest case to solve?” (like fib 0 = 1), and then work through increasingly complex scenarios (like fib 1 = ..., fib 2 = ..., fib 3 = ... and so on) until it “clicks.” Similarly, here it might help to think through “what’s the simplest list I can create?” first, then “what’s the next most simple list I can create?” and keep expanding until it “clicks.”

3 Likes

Just to echo the above reply, List a in Cons a (List a) is not a data constructor. It’s literally the type List a. This type definition is recursive. Here’s my suggestion for how to understand it:

First, note that there’s a type parameter a in the definition. This ranges over all types, so to make things simpler, let’s fix it to e.g. Int. So now we’re trying to understand List Int.

Next, we consider what values live in the type List Int. Here are some:

Nil :: List Int
Cons 100 Nil :: List Int
Cons 5 Nil :: List Int
Cons 5 (Cons 300 Nil) :: List Int
1 Like

To echo the echoes, Haskell 98 syntax for declaring datatypes is confusing. Yes Cons a (List a) is mixing up term-level names with type-level. It’s clearer to use GADT-style syntax:

{-# LANGUAGE GADTSyntax #-}
data List a where
Nil :: List a
Cons :: a → List a → List a

Now we can clearly differentiate the term-level stuff (to the left of ::) from the type-level stuff (to the right). And we can see (roughly speaking) that a data constructor is a function spelled upper-case.

4 Likes
e :: List Int
e = Cons 5 (Cons 6 (Cons 7 Nil)) :: List Int

I didn’t see it was recursive at first. I was just poking around in the dark. I get it now.

2 Likes

I’m going to laugh off the List / [] hangup :smile:
Amazing how I can get thrown off sometimes.