Haskell nested iteration on the same list starting from first loop

I need to do a nested iteration over the same list twice, but the second loop should start where the first one is currently at.

Here’s an example using a for loop:

List l, tuple_l;

for (int x = 0; x < l.length; x++) {
    for (int y = x; y < l.length; y++) {
        tuple_l.push((l[x], l[y]))

And here’s an example using Python’s list comprehension:

[(x, y) for i, x in enumerate(l) for y in l[i:]]

I know how to do this iteration in Haskell iterating over the entire array twice…:

[(x, y) | x <- l, y <- l]

…but I’m not sure how I would go to start the second iteration on what comes after x. Ideally, it would be able to do something like this:

[(x, y) | (x:xs) <- l, y <- xs]  -- Doesn't work 

Obs.: I’m aware a similar question was already answered:
Haskell version of double loop

However, that approach only works for integer ranges. I guess I could somehow use that approach and access the list items by index, but that’s not very haskell/functional-like.

>Solution :

You can exploit tails as follows:

[(x, y) | (x:xs) <- tails l, y <- x:xs, ...]

tails generates all the possible suffixes, e.g. tails [1,2,3] == [[1,2,3], [2,3], [3], []]. Extracting (x:xs) <- tails l we therefore get each element x and the list of its next elements xs. The empty tail [] is silently discarded by the list comprehension. Extracting y <- x:xs completes the task.

Thanks to laziness, iterating over tails l has the same efficiency of iterating over l directly. Indeed, no new list is allocated, only pointers to the already existing l are used.

Leave a Reply