find all pairs with the given sum in an unsorted array of numbers closed

When you’re given an unsorted list, sometimes the best first step is to sort it. So let’s start out:

import Data.List (sort)
sums :: (Num a, Ord a) => [a] -> a -> [(a,a)]
sums xs s = ...
  where
    sorted = sort xs

Cool. What’s next? Let’s work through the sorted list from both sides at once. Lists are bad for that, so let’s use sequences here.

import Data.List (sort)
import Data.Sequence (Seq (..), fromList)

sums :: (Num a, Ord a) => [a] -> a -> [(a,a)]
sums xs s = go sorted
  where
    sorted = fromList (sort xs)
    go Empty = []
    go (_ :<| Empty) = []
    go (a :<| [email protected](as :|> b)) = case compare (a + b) s of
      EQ -> (a,b) : go as
      LT -> go asb
      GT -> go (a :<| as)

This will give results in a different order than your example, but it works in O(n log n) time instead of O(n^2) time—much faster for long lists.

There’s still an unfortunate inefficiency here: we may take an element off a sequence and put it back on multiple times. It’s not a big deal, but it’s really easy to fix.

import Data.List (sort)
import Data.Sequence (Seq (..), fromList)

sums :: (Num a, Ord a) => [a] -> a -> [(a,a)]
sums xs s = start sorted
  where
    sorted = fromList (sort xs)
    start Empty = []
    start (_ :<| Empty) = []
    start (a :<| (as :> b)) = go a as b

    go a as b = case compare (a + b) s of
      EQ -> (a,b) : start as
      LT
        | a' :<| as' <- as
        -> go a' as' b
        | otherwise -> []
      GT
        | as' :|> b' <- as
        -> go a as' b'
        | otherwise -> []

As was pointed out in a now-deleted comment, Data.Sequence is really overkill here. A wide variety of deque-like, multiset-like, and double-ended priority queue structures will work, many of them simpler and/or faster than Data.Sequence.