Range of values in Haskell list comprehension

Question

I'm giving a shot at functional programming, right now using Haskell and practicing list comprehensions. I'm trying to define a function to generate a list of squares...

So far, I have this function:

squares = map (^2) [2..]

What I want to do now is to generate squares only between a range low -> high. I'm generally trying to figure out how to specify a range of values in a Haskell list comprehension. Could someone lend a hand?

Answer 1

What I want to do now is to generate squares only between a range low -> high […] in a Haskell list comprehension

I presume you mean that you want to select the squares that are in this range, rather than the inputs in a particular range, but I’ll go over both. Also, you’re not using a list comprehension currently, just a list, but I’ll also show how to use both.

First of all, your original code can be expressed with map and a list, or with a list comprehension.

squares = map (^ 2) [2 ..]

squares = [x ^ 2 | x <- [2 ..]]

There is no difference in result between the two; the first just avoids naming the intermediate variable x using an operator section (^ 2) = \ x -> x ^ 2.

In a list comprehension, you can include guards, which are Boolean expressions that filter the resulting list at that point. The function equivalent is filter.

squaresBetween (low, high)
  = filter (\ s -> s >= low && s <= high)
    $ map (^ 2) [2 ..]

squaresBetween (low, high)
  = [x ^ 2 | x <- [2 ..], x ^ 2 >= low && x ^ 2 <= high] 

Instead of repeating the x ^ 2 expression, you can bind it to a variable in a comprehension using let:

squaresBetween (low, high) =
  [ s
  | x <- [2 ..]
  , let s = x ^ 2
  , s >= low && s <= high
  ]

And instead of the Boolean expression, you can use the function inRange from Data.Ix (in base), which is equivalent:

import Data.Ix (inRange)

squaresBetween (low, high)
  = filter (inRange (low, high))
    $ map (^ 2) [2 ..]

squaresBetween (low, high) =
  [ s
  | x <- [2 ..]
  , let s = x ^ 2
  , inRange (low, high) s
  ]

This approach with guards or filter is suitable when the input is a finite list. However, because the input list here is an infinite stream of numbers ([2 ..] = enumFrom 2), both of these functions will also produce infinite streams. The language has no way of knowing, in general, that the comprehension will filter out all of the values > high, so it will continue producing and discarding elements, and never reach the end. E.g. in GHCi, evaluating this will hang before printing the end of the list ].

> squaresBetween (0, 100)
[4,9,16,25,36,49,64,81,100

You can type Ctrl+C to exit this computation, which will appear as ^C. GHCi will print Interrupted. and return to the prompt.

One solution to this is to use functions such as takeWhile and dropWhile to filter out elements instead of a guard / filter. takeWhile selects the longest prefix of a list matching a condition, and dropWhile deletes a prefix.

squaresBetween (low, high)
  = takeWhile (<= high)     -- 3. Keep those not over ‘high’.
    $ dropWhile (< low)     -- 2. Discard those under ‘low’.
    $ map (^ 2) [2 ..]      -- 1. Generate a stream of squares.

This can be broken down into smaller parts and composed together:

between (low, high) = takeWhile (<= high) . dropWhile (< low)

squaresBetween range = between range $ map (^ 2) [2 ..]

You can of course combine the two styles, in whichever form you find easiest to understand.

squaresBetween range = between range [x ^ 2 | x <- [2 ..]]

If you wanted to select the numbers whose squares are in the given range, then a good approach is to pair each value with its square, then use takeWhile and dropWhile with conditions on those pairs:

squaresBetween (low, high)

  -- 3. Select only the numbers, not their squares.
  = map fst

    -- 2. Keep and discard pairs by their second element.
    $ takeWhile (\ (_x, s) -> s <= high)  
    $ dropWhile (\ (_x, s) -> s < low)

    -- 1. Generate (number, square) pairs.
    $ [(x, x ^ 2) | x <- [2 ..]]

squaresBetween (0, 100) would then generate [2,3,4,5,6,7,8,9,10]. And these lambdas can be written as compositions instead: (<= high) . snd, i.e. “the second element is ≤ high”.

Another solution is to use a finite input range at the beginning, since you know that no value greater than the square root of high will exceed high. Then a filter or guard is suitable:

squaresBetween (low, high) =
  [ s
  | x <- [2 .. limit]
  , let s = x ^ 2
  , s >= low && s <= high
  ]
  where
    limit = round (sqrt (fromIntegral high)) + 1

And it produces a finite result.

> squaresBetween (0, 100)
[4,9,16,25,36,49,64,81,100]

fromIntegral converts from an integer to a fractional number, sqrt takes the square root, and round converts it back to the nearest integer (using “banker’s rounding” / “round to even”).

Answer 2

You can work with takeWhile and dropWhile to check items and take/drop as long as the predicate is satisfied, so:

squares = (dropWhile (< low) . takeWhile (<= high) . map (^2)) [2..]

For example for low = 5 and high = 123, we get:

Prelude> (dropWhile (< 5) . takeWhile (<= 123) . map (^2)) [2..]
[9,16,25,36,49,64,81,100,121]