Two Sum Implementation on Haskell Brute Force and Optimized approach

Question

Two Sum Problem:

Given an array of integers A and an integer K return True if there are two elements two elements xi, xj (i != j) such that xi + xj = K. Return False otherwise.

I am implementing the classical two sum problem but I am currently practising Functional programming so I picked Haskell. I wrote a naive implementation which I expect is O(n²) (not sure though).

In the brute force implementation I just try every pair of numbers until I find the ones that meet the criteria;

-- O(n^2) implementation
twoSum :: [Int] -> Int -> Bool
twoSum [] k = False
twoSum (x:[]) k = False
twoSum (x:y:[]) k = k == x + y
twoSum (x:y:xs) k 
        | k == x + y = True 
        | otherwise = twoSum (x:xs) k || twoSum (y:xs) k

Then I tried to optimize it. I use a Set to store seen numbers, and then traverse every element x of the array. If K - x is in the Set, it means I found the pair that satisfies the condition.

Per my analysis I think the time complexity is O(n log n) because set implementation in Haskell is O(log n) in insert and check membership:

import qualified Data.Set as S
import Prelude

-- O(n log n) Implementation 
twoSumOpt:: [Int] -> Int -> Bool
twoSumOpt [] k = False
twoSumOpt (x:[]) k = False
twoSumOpt (x:y:[]) k = k == x + y
twoSumOpt (x:y:xs) k 
        | k == x + y = True 
        | otherwise = twoSum' (y:xs) k (S.insert x seen)
    where
        seen = S.fromList([])
        twoSum' :: [Int] -> Int -> S.Set Int -> Bool
        twoSum' (x:[]) k s = S.member (k - x) s
        twoSum' (x:y:[]) k s = k == x + y
        twoSum' (x:xs) k s 
            | S.member (k - x) s = True
            | otherwise = twoSum' xs k (S.insert x s)

I tested with some inputs and profiled solutions:

ghci> twoSumOpt [1, 2, -4, 3, 5, -7, 8] (-2)
True
(0.01 secs, 892,912 bytes)
ghci> twoSumOpt [1..10000000] 10000001
True
(8.51 secs, 8,154,041,496 bytes)
ghci> twoSumOpt [1..100000000] 100000001
True
(95.83 secs, 91,669,673,632 bytes)

Question: am I following the correct Haskell patterns? (the O(N²) implementation didn't finish with my inputs so I assume I got the improvement in performance).

And finally, can we do better in Haskell? Is there a way to implement an amortized insertion and lookup of O(1) so I can do this in O(N)?

Answer 1

Sorry, I know this is stale.

First things first, from a code quality perspective, it's usually not good to have redundant cases. e.g. [x, y] and x:y:xs will both match 1:2:[], and you'll get the behavior you want regardless of which branch of your code it goes to, so only keep the more general one. (Don't worry about the tiny bit of extra work that will happen from the extra recursion, we don't know how it will compare to the extra work that's saved by checking one less pattern!)
It's a little harder to see how this applies in the case of twoSum' than twoSumOpt, but it does (at least once you add a [] case so the pattern match is total).

In a similar vein, why do we need any cases at all for twoSumOpt? twoSum' is already doing basically all of the work, just let it do everything. This gets us as far as:

twoSumOpt :: [Int] -> Int -> Bool
twoSumOpt = twoSum' $ S.fromList []
    where twoSum' :: S.Set Int -> [Int] -> Int -> Bool
          twoSum' _ [] _ = False
          twoSum' s (x:xs) k
            | S.member (k - x) s = True
            | otherwise = twoSum' (S.insert x s) xs k

Can/should we do it in one line? I'm not sure. Our worst-case time will always be when we traverse the entire list, and load it all into our Set, so trying to short-circuit on matches only helps our optimistic paths. If we solve this more bluntly, it'll be a bit easier to read. IDK how it'll affect performance; I don't think it can make the worst case worse by more than a constant 2 factor.

twoSumOpt :: [Int] -> Int -> Bool
twoSumOpt xs k = any (`S.member` s) xs
  where s = S.fromList $ (k -) <$> xs

I'm unaware of any algorithms for this problem with fundamentally better worst-case performance, but it seems like containers's Data.Set implementation, while nice and general purpose, isn't the most performant. You could experiment with IntSet or HashSet; it should be an easy swap.