A few soulutions to SUM10 (finding pairs in a list where their sum is 10)

sum10.hs

module Main where

import Control.Monad (guard)
import Data.List (tails, sort, group)
import qualified Data.Discrimination as D  -- package `discrimination`
import qualified Data.IntSet as IS  -- package `containers`

example :: [Int]
example = [-7,1,2,3,5,5,7,17]

-- O(n^2) with duplictes
sum10_super_naive :: [Int] -> [(Int, Int)]
sum10_super_naive ns = do
  n1 <- ns
  n2 <- ns
  guard $ n1 + n2 == 10
  return (n1, n2)

-- O(n^2) correct
sum10_naive :: [Int] -> [(Int, Int)]
sum10_naive ns = do
  (n1, ns') <- zip ns $ tail $ tails ns
  n2 <- ns'
  guard $ n1 + n2 == 10
  return (n1, n2)

-- O(n log n)
sum10 :: [Int] -> [(Int, Int)]
sum10 ns = go ns' (reverse ns') where
  ns' = nubSorted $ sort ns
  nubSorted = map head . group
  go [] _ = []
  go _ [] = []
  go na1@(n1:ns1) na2@(n2:ns2)
    | n1 > n2       = []
    | n1 + n2 <  10 = go ns1 na2
    | n1 + n2 >  10 = go na1 ns2
    | n1 + n2 == 10 = (n1, n2) : go ns1 ns2


-- O(n) - without hashing
sum10_optimized :: [Int] -> [(Int, Int)]
sum10_optimized ns = go (IS.toAscList set) (IS.toDescList set) where
  set = D.toIntSet ns
  go na1@(n1:ns1) na2@(n2:ns2)
    | n1 > n2       = []
    | n1 + n2 <  10 = go ns1 na2
    | n1 + n2 >  10 = go na1 ns2
    | n1 + n2 == 10 = (n1, n2) : go ns1 ns2
  go _ _ = []

main :: IO ()
main = print $ sum10_optimized $ example