Haskell Lists

Now that we have seen how to define our own list type, let's quickly look at the list type built right into Haskell. A list storing elements of type a has type [a]. A list of Ints has type [Int], a list of Strings has type [String], and a list of lists of Booleans has type [[Bool]].

You can see why this type needs to be built right into the language: the name of a list type is not the name of a type constructor followed by the type of the elements: it is the type of the elements enclosed in square brackets. This requires special support from the parser. It is in fact only the parser support for the special syntax for lists that requires special treatment. We could define the list type like this in pseudo-Haskell:

data [] a
   = []
   | a : [a]

In fact, this is what GHCi tells us is the definition of lists:

GHCi

>>> :info []
type [] :: * -> *
data [] a = [] | a : [a]
    -- Defined in ‘GHC.Types’
instance Applicative [] -- Defined in ‘GHC.Base’
instance Eq a => Eq [a] -- Defined in ‘GHC.Classes’
instance Functor [] -- Defined in ‘GHC.Base’
instance Monad [] -- Defined in ‘GHC.Base’
instance Monoid [a] -- Defined in ‘GHC.Base’
instance Ord a => Ord [a] -- Defined in ‘GHC.Classes’
instance Semigroup [a] -- Defined in ‘GHC.Base’
instance Show a => Show [a] -- Defined in ‘GHC.Show’
instance MonadFail [] -- Defined in ‘Control.Monad.Fail’
instance Read a => Read [a] -- Defined in ‘GHC.Read’
instance Foldable [] -- Defined in ‘Data.Foldable’
instance Traversable [] -- Defined in ‘Data.Traversable’

So a list of as is either empty, [], or it consists of an element of type a followed by a list of as, the tail. The (:) operator for lists behaves exactly the same as our Cons type constructor for our own home-baked list type, only we use it in infix notation because it's an operator.

Given that [] is the equivalent of Empty, and (:) is the equivalent of Cons—they are data constructors according to our pseudo-Haskell definition of the list type above—it shouldn't come as a surprise that we can pattern match against them. Here's the equivalent of listMap for proper Haskell lists.

map :: (a -> b) -> [a] -> [b]
map f = go
  where
    go []     = []
    go (x:xs) = f x : go xs

This function, filter, and a whole range of other list functions are available as part of the Haskell standard library. Many of them, including map, are included in the Prelude and thus are available out of the box. Others are available only after importing Data.List. Use Hoogle to find out what functions Data.List provides. The list is long. We will use some of them later in this book.

Exercise

Implement a function

filter :: (a -> Bool) -> [a] -> [a]

that matches the behaviour of the listFilter function from the previous section. This function is available as part of the Prelude, but implementing it yourself is a good exercise.

Solution

filter pred = go
  where
    go []                 = []
    go (x:xs) | pred x    = x : go xs
              | otherwise =     go xs