Understanding Haskell code which applies the `tails` function to an infinite list within a list comprehension

Question

After submitting my solution to Project Euler's problem 50 earlier today, I was scrolling through the problem's forums, taking a look at other folks' solutions/execution times.

After a while, I started to feel quite proud of my code which solved it in ~3 seconds (my code used the Primes library and was compiled with O2)...

...and then I came across the code below which solved it in ~0.05 seconds...in interpreted mode (i.e., ghci).

Can someone explain how/why the code below solves this particular problem?

The mind-twisting part is the application of the tails function to the infinite list of primes (primes) within a list comprehension. I'm having a hard time understanding how we guarantee that we look at all possible sublists of consecutive primes and not just those generated by tails.

(My usual strategy of trying bits and pieces of code in ghci doesn't work in this situation because primes is infinite...)

The problem: We're asked to find the largest prime number below 1,000,000 which is the result of summing consecutive prime numbers. For example, the largest prime number below 100 which is the sum of consecutive primes is 41 (2 + 3 + 5 + 7 + 11 + 13).

import Data.List (tails)
import Data.Numbers.Primes

under n xs = takeWhile (< n) xs

takeUntil p xs = foldr (\x r-> if p x then [x] else x:r) [] xs

res :: [((Int, Int), (Int, Int))] 
-- ((top_length, sums_to), (total_length, starting_prime))

res = [(r,(length s,x)) | (x:xs) <- tails primes
                        , let s = zip [1..]
                                $ under 100
                                $ scanl (+) x xs
                        , let r = ...] 

main = mapM_ print $ takeUntil ...

Answer 1

In general, there's no problem with taking tails of primes, because Haskell is lazy (the evaluation is on-demand).

Here specifically there's even less problem because each sublist is trimmed with under 100 = takeWhile (< 100) - only a finite prefix is taken.

(x:xs) <- tails primes just goes through all suffixes of primes - i.e. primes starting from x=2; then primes starting from x=3, then 5,7,11, .... The pattern only demands the head element x, and the tail xs of the primes list, and even their values aren't immediately requested, only the so-called "spine" of primes list is forced, 1 notch at a time (of course making sure primes starts with at least one element x will automatically compute the actual value of x, but that's another matter).

So (x:xs) <- tails primes operates on consecutive suffixes of the primes list. Try tails [1..10] to see what's going on there.

---

When you type

GHCi> primes

at the GHCi prompt, you're actually requesting all the elements of primes list to be printed as the output. But

GHCi> under 100 primes

will only request those below 100, and not more than one element after that. It uses the built-in takeWhile that examines elements in primes, one after another, until one is found that fails the predicate (in this case, is bigger than 100). The terminating element is not included in the result.

The user-defined takeUntil differs from that only in that it also includes the terminating element in its result (and the meaning of predicate is flipped - it signals when to stop).

The scanl (+) is the usual way to calculate the sequence of partial sums of a sequence:

Prelude> scanl (+) 1 [2..10]
[1,3,6,10,15,21,28,36,45,55]

---

The code

 [ (r,(length s,x)) | (x:xs) <- tails primes
                    , let s = zip [1..]
                            $ under 100
                            $ scanl (+) x xs
                    , let r = last $ filter (isPrime.snd) s] 

means:

for each suffix of primes        -- [[2,3,5,7...],[3,5,7,11...],...]
  let 
    x  = head suffix             -- for all primes from x
    xs = tail suffix             --   i.e. xs
    t1 = scanl (+) x xs          -- calculate partial sums
    t2 = under 100 t1            -- stopping when the sum reaches 100
    s  = zip [1..] t2            -- index each sum by the length of subsequence,
    t3 = filter (isPrime.snd) s  -- keep only such that summed to a prime,
    r  = last t3                 -- and take the one created from the
  in                             --    longest subsequence, starting from x
    emit (r,(length s,x))        -- and collect the data

So we get the list of entries ((top_length, sums_to), (total_length, starting_prime)) for each consecutive prime number, starting_prime = 2,3,5,7,11, ... .

The takeUntil expression in main determines when it's okay to stop, as there's no possibility of improving the result anymore.

Answer 2

To work around the infinite list problem, just define:

primesUpTo100 = takeWhile (< 100) primes

and use primesUpTo100 in the definition of res in place of primes.

Next, change the definition of res to return different values so you can see what is going on, e.g.:

res = do
  (x:xs) <- tails primesUpTo100
  let s = zip [1..] $ under 100 $ scanl (+) x xs
  let r = last  $ filter (isPrime.snd) s
  return (x, take 10 xs, s)

Now you can see what s is and how it is related to x and the first 10 elements of xs.

If the list res is too long just evaluate take 10 res. Another tip is to define a helper function:

import Control.Monad
pp xs = forM_ xs print

This will print out a list which each element on a new line which should make things easier to read. E.g.:

pp (take 10 res)

Using all of these ideas I bet you can figure it out. It's actually a brute-force search for the longest sequence, but the use of scanl might avoid the recalculation of sums.