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`

.

CLICK HERE to find out more related problems solutions.