HASKELL LIST COMPREHENSION

REVISED: Tuesday, February 6, 2024

Haskell List Comprehension.

I. HASKELL LIST COMPREHENSION

A. HASKELL LIST COMPREHENSION EXAMPLE

[ x | x <- S,  p x ]

For every x such that x is an element of the set S and satisfies the predicate p x.

| pipe is pronounced "such that".
<- arrow is pronounced "drawn from".
S set is pronounced "generator".
, comma before the predicate is pronounced "if".
p x is pronounced "condition" or "predicate".

In the example shown below,  x is a function, such that every x drawn from the generator [0,1,2,3,4,5,6,7,8,9] is less than or equal to five.

Prelude>  [ x | x <- [0,1,2,3,4,5,6,7,8,9], x <= 5 ]
[0,1,2,3,4,5]
it :: (Ord t, Num t) => [t]
Prelude>  

The part before the pipe |, is the output function x. The part after the pipe |, is the qualifier. x is drawn from the input set generator [0,1,2,3,4,5,6,7,8,9]. For every element in the generator [0,1,2,3,4,5,6,7,8,9] that we have bound to x we get that element x if it satisfies the condition, predicate, guard of being <= 5.

B. HASKELL LIST COMPREHENSION GUARDS

A guard is a filter, a boolean predicate that evaluates to True or False; for example, odd , isAlpha, and all of the boolean expressions such as >, <, ==, etc.

You can use as many generators and guards as you want in a list comprehension.

C. HASKELL EMPTY LIST

You always want to know if a function is associative, (a + b) + c  =  a + (b + c); and its identity element.

Prelude>  sum []   -- 0 is the neutral element or identity for sum.
0
it :: Num a => a
Prelude>

Prelude>  product []   -- 1 is the neutral element or identity for times.
1
it :: Num a => a
Prelude>  

D. HASKELL LIST COMPREHENSION GENERATOR EXAMPLE

Prelude>  let y = [ x*x | x <- [1..3] ]
y :: (Num t, Enum t) => [t]
Prelude>

Prelude>  y
[1,4,9]
it :: (Num t, Enum t) => [t]
Prelude>

Prelude>  :type y
y :: (Num t, Enum t) => [t]
Prelude>  

[ x*x | x <- [1..3] ]
=
[ 1*1] ++ [ 2*2 ] ++ [ 3*3]
=
[ 1 ] ++ [ 4 ] ++ [ 9 ]
=
[1, 4, 9]

E. HASKELL LIST COMPREHENSION GENERATOR AND FILTER EXAMPLE

Prelude>  let y = [ x*x | x <- [1..3], odd x ]
y :: Integral t => [t]
Prelude>

Prelude>  y
[1,9]
it :: Integral t => [t]
Prelude>

[ x*x | x <- [1..3], odd x ]
=
[ 1*1 | odd 1 ] ++ [ 2*2 | odd 2 ] ++ [ 3*3 | odd 3 ]
=
[ 1 | True] ++ [ 4 | False ] ++ [ 9 | True]
=
[ 1 ] ++ [  ] ++ [ 9 ]
=
[1,9]

F. HASKELL LIST COMPREHENSION TWO GENERATORS EXAMPLE

Prelude>  let y = [ (i,j) | i <- [1..3], j <- [i..3] ]
y :: (Num t, Enum t) => [(t, t)]
Prelude>

Prelude>  y
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]
it :: (Num t, Enum t) => [(t, t)]
Prelude>  

[ (i,j) | i <- [1..3], j <- [i..3] ]
=
[ (1,j) | j <- [1..3] ] ++
[ (2,j) | j <- [2..3] ] ++
[ (3,j) | j <- [3..3] ] 
=
[ (1,1), (1,2), (1,3) ] ++
[ (2,2), (2,3) ] ++
[ (3,3) ] 
=
[ (1,1), (1,2), (1,3), (2,2), (2,3), (3,3) ]

G. HASKELL LIST COMPREHENSION TWO GENERATORS AND FILTER EXAMPLE

Prelude>  let y = [(i,j) | i <- [1..3], j <- [1..3], i <= j]
y :: (Ord t, Num t, Enum t) => [(t, t)]
Prelude>

Prelude>  y
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]
it :: (Ord t, Num t, Enum t) => [(t, t)]
Prelude>  

[(i,j) | i <- [1..3], j <- [1..3], i <= j]
=
[ (1,j) | j <- [1..3], 1 <= j ] ++
[ (2,j) | j <- [1..3], 2 <= j ] ++
[ (3,j) | j <- [1..3], 3 <= j ]
=
[(1,1)|1<=1] ++ [(1,2)|1<=2] ++ [(1,3)|1<=3] ++
[(2,1)|2<=1] ++ [(2,2)|2<=2] ++ [(2,3)|2<=3] ++
[(3,1)|3<=1] ++ [(3,2)|3<=2] ++ [(3,3)|3<=3]
=
[(1,1)]      ++ [(1,2)]      ++ [(1,3)]      ++
[]              ++ [(2,2)]      ++ [(2,3)]      ++
[]              ++ []              ++ [(3,3)]
=
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]

H. LIST COMPREHENSION VERSUS RECURSION

-- Comprehension
squaresComp ::[Integer] -> [Integer]
squaresComp xs = [ x*x | x <- xs ]

-- Recursion
squaresRec :: [Integer] -> [Integer]
squaresRec []        = []
squaresRec (x:xs) = x*x : squaresRec xs

II. CONCLUSION

In this tutorial, you have been introduced to Haskell list comprehension.

III. REFERENCES

Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.

Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.

Goerzen, J. & O'Sullivan, B. &  Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.

Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.

Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.

Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.