Haskell: Find two related elements in a list

Question

I am new to Haskell/FP. I want to solve this task:

This list is given: [1721, 979, 366, 299, 675, 1456]

Find the two elements that sum to 2020 and multiply them. The solution is 1721 * 299.

I think in Haskell, the tools I can use to solve this problem are list comprehension and fold (or a combination of them). But I don't understand how I can write a list comprehension that takes into account other elements of the same list, and not just one element at the time.

This is what I came up with after several hours (ints is the list):

print [(x,y, x*y) | x <- ints, y <- ints, x+y == 2020]

It actually prints the right answer. But I think my solution is dirty:

• I feed the input list twice into the list comprehension. Is this correct? It seems like overhead/duplication to me. I am sure there is a better way.
• The return of the function is a list with two same entities (I assume this is because of what I described in the last bullet): [(1721,608,514579),(1721,608,514579)] - of course I could get a single element with head, but that doesn't solve the root of the problem.

Answer 1

The reason this will emit the same value twice is because you have two iterators over the list. This thus means that at some point x will take as value 1721 and y will take as value 299; but later in the program the opposite will be true: x will take 299; and y will take 1721.

We can easily fix that problem by using tails :: [a] -> [[a]]:

import Data.List(tails)

[(x,y, x*y) | (x:ys) <- tails ints, y <- ys, x+y == 2020]

here for each suffix of ints, we will take x as the first element, and ys as the remaining elements, and then we enumerate over ys.

But this still takes quadratic time. This kan be done on O(n log n) by sorting the list, and then use recurse where we enumerate over both ends of the list until we find a value equal to 2020. Another option is to make use of a collection like a HashSet. Then we first store the elements in the HashSet, and then for each element x in the list, we check if 2020 - x is in the HashSet. I leave these as an execise.