© Stefania Loredana Nita and Marius Mihailescu 2019
Stefania Loredana Nita and Marius MihailescuHaskell Quick Syntax Referencehttps://doi.org/10.1007/978-1-4842-4507-1_9

9. List Comprehension

Stefania Loredana Nita1  and Marius Mihailescu1
(1)
Bucharest, Romania
 

Chapter 6 introduced lists, and now you will learn another way to represent a list. Do you remember how sets are represented using mathematical symbols? Well, you will do that with lists. Further, you will learn more complex functions that you can apply on lists.

Introduction

Let’s say you have the set A = {x ∈ ℕ| 5 ≤ x ≤ 10}. If you pay a little attention, you will observe that in natural terms A is a list. Haskell provides you with a way to represent such lists, as shown here:
Prelude> let set = [x | x <- [5..10]]
Prelude> set
[5,6,7,8,9,10]

This type of representation is called list comprehension , and x is called a generator.

This can be complicated. Let’s say you want the numbers between 100 and 200 that are divisible by 17. Note that you can add a condition (or a predicate) called a guard.
Prelude> [x | x <- [100..200], x `mod` 17 == 0]
[102,119,136,153,170,187]
What if you want those numbers divisible with 17 and 10? You do that like this:
Prelude> [x | x <- [100..200], x `mod` 17 == 0, x`mod` 10 == 0]
[170]

Observe that we added two predicates, separated by a comma.

But you also can do it like this:
Prelude> [x | x <- [100..200], x `mod` 17 == 0 && x`mod` 10 == 0]
[170]
You can add more variables like this:
Prelude> [ x+y | x <- [1,7,12], y <- [5,9,14]]
[6,10,15,12,16,21,17,21,26]
Prelude> [ x+y | x <- [1,7,12], y <- [5,9,14,17]]
[6,10,15,18,12,16,21,24,17,21,26,29]

In this case, every element from the first list is summed up with every element from the second list. It is similar to a Cartesian product , but in this case you sum up the elements of pairs in the Cartesian product.

Let’s add another restriction to this example, as shown here:
Prelude> [ x+y | x <- [1,7,12], y <- [5,9,14,17], x+y >20]
[21,24,21,26,29]
These operations work the same on the strings.
Prelude> let l1 = ["my", "your"]
Prelude> let l2 = ["book", "pencil", "PC"]
Prelude> [elem1 ++ " " ++ elem2 | elem1 <- l1, elem2 <- l2]
["my book","my pencil","my PC","your book","your pencil","your PC"]
An important aspect about lists is the _ symbol. Here’s an example:
Prelude> let numbers = [1,3..100]
Prelude> [0 | _ <- numbers]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

This means every element of the list is replaced by 0. Instead of _, you could use a variable, but it is more convenient in this way, as syntactic sugar. For short, syntactic sugar is just another representation for expressions written in an analytic way and does not add functionality. The main purpose of syntactic sugar is to make the code more readable.

You can use an if..then..else statement in a list comprehension. Let’s say you want to check whether the positive numbers in a list are odd or even.
Prelude> parity list = [ if x `mod` 2 == 0 then "even" else "odd" | x <- list, x >= 0]
Prelude> parity [-100,-97..25]
["even","odd","even","odd","even","odd","even","odd"]
This is a little confusing because you don’t know which are the numbers. Let’s improve it.
Prelude> parity list = [ if x `mod` 2 == 0 then show x ++ " even" else show x ++ " odd" | x <- list, x >= 0]
Prelude> parity [-100,-97..25]
["2 even","5 odd","8 even","11 odd","14 even","17 odd","20 even","23 odd"]

Now it is better. The show function converts its parameter into a String.

Other Functions on Lists

Now that you know how to work with functions, you’ll write your own functions to apply on lists. You will start by using some other functions from the Data.List module (all other functions on lists that you have learned about so far belong to this module), and then you will sort elements on a list of integers.

In the first example, you will use the predefined map function . The general definition of map is as follows:
map :: (a -> b) -> [a] -> [b]
The statement map f list will produce a new list obtained by applying f to every element of list. Write a function double in the Double.hs file with the following statements:
double :: Integer -> Integer
double x = 2*x
Then, load the file and apply the double function to the elements of a list.
Prelude> :load Double
[1 of 1] Compiling Main             ( Double.hs, interpreted )
Ok, one module loaded.
*Main> map double [-8,-3..30]
[-16,-6,4,14,24,34,44,54]
Next, you want to check whether an element of a list is even and whether it is greater than 20. You can use the check function .
check :: Integer -> Bool
check x =
  x `mod` 2 == 0 && x > 20
Further, you can use the any function that tells you whether there are elements in the list that accomplish a condition.
*Main> any check [1,2,3,4]
False
*Main> any check [1,2,3,4, 22]
True
A similar function is all, which tells you whether all the elements of the list accomplish a condition.
*Main> all check [1,2,3,4]
False
*Main> all check [1,2,3,4, 22]
False
*Main> all check [22, 24]
True
The following are other useful functions for lists:

  • find returns the first element of the list that satisfies a predicate, or Nothing otherwise.

  • filter returns all elements of the list that satisfy a condition.

  • elemIndices/elemIndex returns all indices of the elements equal to a given item or the first index of the element equal to a given item or Nothing if there is no such element.

  • findIndex/findIndices returns all indices of the elements that make up a predicate or the first index of the element that makes up a predicate or Nothing if there is no such element.

  • The zip family of functions creates tuples from lists based on different criteria.

Go ahead and practice these functions.

Next, let’s sort a list. For this example, you can use the quicksort technique . Quicksort takes an element as a pivot and reorders the list so that all elements with a lesser value than the pivot move onto the left side of the pivot and the elements with a greater value than the pivot move to the right side of the pivot (assuming you are sorting a list in increasing order). This can be done recursively easily.
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (y:ys) = (qsort ls) ++ [y] ++ (qsort gt)
    where
        ls  = filter (< y) ys
        gt = filter (>= y) ys
This works as follows:
*Main> qsort [10, 1, 5]
[1,5,10]
*Main> qsort [10, 1, 5, -7, 0]
[-7,0,1,5,10]

Summary

In this chapter, you learned about the following:

  • How to represent a list in a comprehension form

  • How to apply your own functions on lists

  • Other useful functions applied on lists

  • How to sort a list, using the quicksort algorithm

References

  1. 1.

    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (MIT Press, 2009)

     
  2. 2.

    A. Nunes-Harwitt, M. Gambogi, and T. Whitaker, “Quick-Sort: A Pet Peeve” in proceedings of the 49th ACM Technical Symposium on Computer Science Education, pp. 547–549 (ACM, 2018)

     
  3. 3.

    M. Lipovaca, Learn You a Haskell for Great Good! A Beginner’s Guide (No Starch Press, 2011)

     
  4. 4.

    M. Aslam, Functional Programming Language–Haskell (2003)

     
  5. 5.

    Data.List, http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-List.html

     
  6. 6.

    List comprehension, https://wiki.haskell.org/List_comprehension

     
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.145.97.109