Working with list functions

In this recipe, we will work with the list data type in Haskell. The list function is one of the most widely used data types in Haskell.

Getting ready

Use Stack to create a new project, list functions, and change into the project directory. Build the project with stack build.

Remove the contents of src/Lib.hs and add the module heading:

    module Lib where

How to do it...

1. Create an empty list:

        emptyList = []

2. Prepend an element to the list:

        prepend = 10 : []

3. Create a list of five integers:

        list5 = 1 : 2 : 3 : 4 : 5 : []

4. Create a list of integers from 1 to 10:

        list10 = [1..10]

5. Create an infinite list:

        infiniteList = [1..]

6. This is the head of a list:

        getHead = head [1..10]

7. This is the tail of a list:

        getTail = tail [1..10]

8. This is all but the last element:

        allbutlast = init [1..10]

9. Take 10 elements:

        take10 = take 10 [1..]

10. Drop 10 elements:

        drop10 = drop 10 [1..20]

11. Get n^th element:

        get1331th = [1..] !! 1331

12. Check if a value is the element of the list.

        is10element = elem 10 [1..10]

13. Do pattern matching on the list. Here we check whether the list is empty or not:

        isEmpty [] = True
        isEmpty _ = False

14. Do more pattern matching. Here we do pattern matching on elements present in the list. 

        isSize2 (x:y:[]) = True
        isSize2 _ = False

15. Concatenate two lists:

         cat2 = [1..10] ++ [11..20]

16. String is actually a list. Check this by creating a list of characters:

        a2z = ['a'..'z']

17. Since string is a list, we can use all list functions on string. Here we get the first character of a string:

        strHead = head "abc"

18. Zip two lists:

        zip2 = zip ['a'..'z'] [1.. ]

19. Open app/Main.hs and use the preceding functions from the list, and also print values:

        module Main where

        import Lib

        main :: IO ()
        main = do
          putStrLn $ show $ (emptyList :: [Int])
          putStrLn $ show $ prepend
          putStrLn $ show $ list5
          putStrLn $ show $ list10
          putStrLn $ show $ getHead
          putStrLn $ show $ getTail
          putStrLn $ show $ allbutlast
          putStrLn $ show $ take10
          putStrLn $ show $ drop10
          putStrLn $ show $ get1331th
          putStrLn $ show $ is10element
          putStrLn $ show $ isEmpty [10]
          putStrLn $ show $ isSize2 []
          putStrLn $ show $ cat2
          putStrLn $ show $ a2z
          putStrLn $ show $ strHead

20. Build the project using stack build and run it using stack run list-functions-exe. Note that Main does not use the infiniteList snippets and does not print them.

How it works...

List is defined as follows:

    data [] a = []       -- Empty list or
       | a : [a]  -- An item prepended to a list, is also a list

There are two data constructors. The first data [] constructor shows an empty list, and a list with no elements is a valid list. The second data constructor tells us that an item prepended to a list is also a list.

Also, notice that the type constructor is parameterized by a type parameter a. It means that the list can be constructed with any type a.

List creation

The first three snippets in the previous section are created using list's data constructors. The third example shows recursive application of the second constructor.

Enumerated list

The fourth and fifth snippets show how to create a list from enumerated values. Enumerated values are those that implement type class Enum and are implemented by ordered types such as Int, Double, Float, Char, and so on. The enumerated type allows us to specify a range using '..' (for example, 1..10, which means numerals 1 to 10,  including 10). It is also possible to drop the to value. For example, 1.. will create an infinite list. It is also possible to specify an increment by specifying consecutive values. For example, 1,3,..10 will expand to 1,3,5,7,9 (note that the last value 10 is not part of it as it does not belong to the sequence).

Head and tail of a list

From the definition of a list, any element, when prepended to a list, is also a list. For example, 1:[2,3] is also a list. Here, 1 is called the head of the list, and 2 is called the tail of the list.

The functions head and tail return head and tail, respectively, of the list. The snippets 6 and 7 show an example of head and tail. Head has a signature - head :: [a] -> a and tail has a signature :: [a] -> [a] .

Operations on a list

Once we have a list, we can do various operations, such as the following ones:

• init :: [a] -> [a]: Take all but the last element of the list. This is shown in snippet 8.
• take :: Int -> [a] -> [a]: Take, at the most, the first n elements of the list (shown as the Int argument). If the list has less than n elements, then it will consume the entire list. This is shown in snippet 9.

  In snippet 9, we worked on an infinite list and took only the first 10 elements. This works in Haskell, because in Haskell, nothing is evaluated until computation needs a value. Hence, even if we have an infinite list, when we take the first 10 elements, only 10 elements of the list are evaluated. Such things are not possible in strict languages. Haskell is not a strict language.

• drop :: Int -> [a] -> [a]: Similar to take, but the drop function drops the first n elements. It will drop the whole list if the list has less than n elements. If we operate on an infinite list, then we will get an infinite list back. Snippet 10 shows an example of drop.

Indexed access

The function names in Haskell do not necessarily start with alphabets. Haskell allows us to use a combination of other characters as well. Many collections, including list, define !! as an indexing function. Snippet 11 uses this.

The function !! takes a list and an index n, and returns the n^th element, starting 0. The signature of !! is  (!!) :: Int -> [a] -> a.

It is important to note that an access to an indexed element in the list is not random. It is sequential and is directly proportional to the index value. Hence, care should be taken to use this function.

Checking whether an element is present

The elem function checks whether a given element is present in the list. The elem function must be able to equate itself with another of its own type. This is done by implementing type Eq class, which allows checking whether two values of a type are equal or not.

Pattern matching on list

Once we know that a list has two data constructors, we can use them in the function argument for pattern matching. Hence, we can use [] for empty list matching, and we can use x:y:[] to match two elements followed by an empty list.

In the snippet 13, we used an empty list pattern for checking whether a list is empty or not.

In the snippet 14, we used x:y:[] to check whether the list has length 2 or not. This might not be a very good thing if we want to check the larger size. There, we might use the length function to get the size of the list. However, be aware of the fact that the length function is not a constant time function, but proportional to the size of the list.

List concatenation

It is possible to concatenate two lists by using the ++ function. The running time of this function is directly proportional to the size of the first list.

Strings are lists

It is important to note that the type String in Haskell is implemented as a list of Char:

    type String = [Char]

Hence, all list operations are valid string operations as well. The snippets 17 and 18 show this by applying list functions on String. Since list is not a random access collection and operations such as concatenation are not constant time operations, strings in Haskell are not very efficient. There are libraries such as text that implement strings in a very efficient way.

There's more…

The preceding list of operations on Haskell list is not exhaustive. You can refer to the Data.List module in the base package (which is installed as a part of GHC). It provides documentation to all the functions that operate on list.