# Difference between revisions of "List comprehension"

m (Fixed the link to the parallel list comprehension documentation) |
(→List monad: Obsoleted speculation.) |
||

(4 intermediate revisions by 2 users not shown) | |||

Line 9: | Line 9: | ||

The result of this list comprehension is <hask>"HELLO"</hask>. |
The result of this list comprehension is <hask>"HELLO"</hask>. |
||

(Of course, in this simple example you would just write <hask>map toUpper s</hask>.) |
(Of course, in this simple example you would just write <hask>map toUpper s</hask>.) |
||

+ | |||

+ | __TOC__ |
||

== Examples == |
== Examples == |
||

Line 73: | Line 75: | ||

The GHC compiler supports parallel list comprehensions as an extension; see [https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#parallel-list-comprehensions GHC 8.10.1 User's Guide 9.3.13. Parallel List Comprehensions]. |
The GHC compiler supports parallel list comprehensions as an extension; see [https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#parallel-list-comprehensions GHC 8.10.1 User's Guide 9.3.13. Parallel List Comprehensions]. |
||

+ | |||

+ | == Skips elements on pattern fails == |
||

+ | <tt>catMaybes</tt> removes Nothing's from a list. [https://hackage.haskell.org/package/base-4.15.0.0/docs/src/Data-Maybe.html#catMaybes Its source]: |
||

+ | |||

+ | <haskell> |
||

+ | catMaybes :: [Maybe a] -> [a] |
||

+ | catMaybes ls = [x | Just x <- ls] |
||

+ | </haskell> |
||

+ | |||

+ | If the <tt>Just x</tt> pattern doesn't match, no element is added to the result! |
||

+ | |||

+ | You can ask [[lambdabot]] on Liberachat ([[IRC]]) to unpack the list comprehension syntax: |
||

+ | |||

+ | In the #haskell channel, or in a private message, say <tt>@undo</tt> and then your list comprehension, it will shoow you how it expands: |
||

+ | |||

+ | <pre> |
||

+ | <youOnIRC> @undo [x | Just x <- xs] |
||

+ | <lambdabot> concatMap (\ a -> case a of { Just x -> [x]; _ -> []}) xs |
||

+ | </pre> |
||

+ | |||

+ | So it doesn't invoke [[MonadFail]] at all, per default. With [https://downloads.haskell.org/ghc/latest/docs/html/users_guide/exts/monad_comprehensions.html MonadComprehensions] it would. |
||

== List monad == |
== List monad == |
||

Line 79: | Line 102: | ||

Later the comprehension syntax was restricted to lists. |
Later the comprehension syntax was restricted to lists. |
||

Since lists are an instance of monads, you can get list comprehension in terms of the <hask>do</hask> notation. |
Since lists are an instance of monads, you can get list comprehension in terms of the <hask>do</hask> notation. |
||

− | Because of this, several Haskell programmers consider the list comprehension unnecessary now. |
||

The examples from above can be translated to list monad as follows: |
The examples from above can be translated to list monad as follows: |

## Revision as of 18:47, 10 January 2022

List comprehensions are syntactic sugar like the expression

```
import Data.Char (toUpper)
[toUpper c | c <- s]
```

where `s :: String`

is a string such as `"Hello"`

.
Strings in Haskell are lists of characters; the generator `c <- s`

feeds each character of `s`

in turn to the left-hand expression `toUpper c`

, building a new list.
The result of this list comprehension is `"HELLO"`

.
(Of course, in this simple example you would just write `map toUpper s`

.)

## Examples

One may have multiple generators, separated by commas, such as

```
[(i,j) | i <- [1,2],
j <- [1..4] ]
```

yielding the result

```
[(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4)]
```

Note how each successive generator refines the results of the previous generator. Thus, if the second list is infinite, one will never reach the second element of the first list. For example,

```
take 10 [ (i,j) | i <- [1,2],
j <- [1..] ]
```

yields

```
[(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10)]
```

In such a situation, a nested sequence of list comprehensions may be appropriate. For example,

```
take 5 [ [ (i,j) | i <- [1,2] ] | j <- [1..] ]
```

yields

```
[[(1,1),(2,1)], [(1,2),(2,2)], [(1,3),(2,3)], [(1,4),(2,4)], [(1,5),(2,5)]]
```

One can also provide boolean guards. For example,

```
take 10 [ (i,j) | i <- [1..],
j <- [1..i-1],
gcd i j == 1 ]
```

yields

```
[(2,1),(3,1),(3,2),(4,1),(4,3),(5,1),(5,2),(5,3),(5,4),(6,1)]
```

Finally, one can also make local let declarations. For example,

```
take 10 [ (i,j) | i <- [1..],
let k = i*i,
j <- [1..k] ]
```

yields

```
[(1,1),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(3,5)]
```

Here is an example of a nested sequence of list comprehensions, taken from code implementing the Sieve of Atkin:

```
[[[ poly x y
| i <- [0..], let x = m + 60*i, test x y ]
| j <- [0..], let y = n + 60*j ]
| m <- [1..60], n <- [1..60], mod (poly m n) 60 == k ]
```

The result is a list of infinite lists of infinite lists.

The specification of list comprehensions is given in The Haskell 98 Report: 3.11 List Comprehensions.

The GHC compiler supports parallel list comprehensions as an extension; see GHC 8.10.1 User's Guide 9.3.13. Parallel List Comprehensions.

## Skips elements on pattern fails

`catMaybes` removes Nothing's from a list. Its source:

```
catMaybes :: [Maybe a] -> [a]
catMaybes ls = [x | Just x <- ls]
```

If the `Just x` pattern doesn't match, no element is added to the result!

You can ask lambdabot on Liberachat (IRC) to unpack the list comprehension syntax:

In the #haskell channel, or in a private message, say `@undo` and then your list comprehension, it will shoow you how it expands:

<youOnIRC> @undo [x | Just x <- xs] <lambdabot> concatMap (\ a -> case a of { Just x -> [x]; _ -> []}) xs

So it doesn't invoke MonadFail at all, per default. With MonadComprehensions it would.

## List monad

In the first versions of Haskell, the comprehension syntax was available for all monads. (See History of Haskell)
Later the comprehension syntax was restricted to lists.
Since lists are an instance of monads, you can get list comprehension in terms of the `do`

notation.

The examples from above can be translated to list monad as follows:

```
do c <- s
return (toUpper c)
```

```
do i <- [1,2]
j <- [1..4]
return (i,j)
```

or

```
liftM2 (,) [1,2] [1..4]
```

```
do j <- [1..]
return
(do i <- [1,2]
return (i,j))
```

```
do i <- [1..]
j <- [1..i-1]
guard (gcd i j == 1)
return (i,j)
```

```
do i <- [1..]
let k = i*i
j <- [1..k]
return (i,j)
```

```
do m <- [1..60]
n <- [1..60]
guard (mod (poly m n) 60 == k)
return $
do j <- [0..]
let y = n + 60*j
return $
do i <- [0..]
let x = m + 60*i
guard (test x y)
return (poly x y)
```