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`.