Haskell nested iteration on the same list starting from first loop

João Haas 0
Viewed 61

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.

haskell list-comprehension list loops
3 Answers

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.

usernAzd0

The straightforward translation of your python code is as follows:

[(x, y) | (i, x) <- zip [0..] l, y <- drop i l, ...]

However, in Python l[i:] is a fast operation (O(1)), but in Haskell drop i l is slow (O(i)).

As you already seem to try it is better to try to get the tail of the list at the point where the x element is. In Haskell you can do that in several ways. Perhaps the easiest is using the tails function:

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

You can do it with a layer of explicit recursion like this:

f xs = case xs of
  [] -> []
  h:t -> [(h, x) | x <- xs] ++ f t

If you had done int y = x + 1; instead of int y = x; in your C code, then you'd use t instead of xs in the list comprehension in my Haskell code.

Joseph Sible-Reinstate Monica0
Related