Haskell split a list into two by a pivot value

Question

I want to split [a] into ([a], [a]) by a pivot value and I have my code

splitList :: (Ord a) => a -> [a] -> ([a],[a])
splitList pivot list = 
    ([x | x <- list, x <= pivot], [x | x <- list, x > pivot])

But it iterates the list twice to generate two lists, is there a way to iterate only once?

Answer 1

There are two possibilities, depending on if you want a tail recursive solution (and don't care about reversing the order of elements), or a solution that consumes its argument lazily.

The lazy solution decides if the first element of the list goes into the first or into the second part and uses a simple recursion to process the rest of the list. This would be the preferred solution in most cases as laziness is usually more important than tail recursion:

splitList :: (Ord a) => a -> [a] -> ([a],[a])
splitList _ [] = ([], [])
splitList p (x : xs)
    | x <= p    = (x : l, r)
    | otherwise = (l, x : r)
  where
    ~(l, r) = splitList p xs

However in some cases you care neither for the ordering of elements nor for laziness, but instead for speed. (For example when implementing a sorting algorithm.) Then a variant that uses an accumulator to build the result (see Accumulating Parameters: Getting rid of the 'almost' in "almost tail recursive" ) to achieve tail recursion would be more appropriate:

splitListR :: (Ord a) => a -> [a] -> ([a],[a])
splitListR pivot = sl ([], [])
  where
    sl acc    []        = acc
    sl (l, g) (x : xs)
        | x <= pivot    = sl (x : l, g) xs
        | otherwise     = sl (l, x : g) xs

Answer 2

It's generally considered good style to avoid hand-rolling your recursion; instead you can use a folding function like so:

splitList pivot = foldr triage ([],[]) 
  where
    triage x ~(lows, highs) 
      | x <= pivot = (x:lows, highs)
      | otherwise  = (lows, x:highs)

Of course it's even better style to make use of a preexisting function that does exactly what you need, i.e. partition. :)

Answer 3

If you want to write this from scratch, you can maintain two lists, one for small items, one for large. First I'll write the wrapper:

splitList :: (Ord a) => a -> [a] -> ([a],[a])
splitList pivot input = spL input [] [] where

OK, so I"m just calling spL and giving it two empty lists to start off with. Because I'm using a where block, I'll not need to pass the pivot around, so only the three lists that are changing get passed. If we haven't got anything left in the input, we're done and should return the answer:

    spL [] smalls larges = (smalls,larges)

Now as you'll see, we'll actually make smalls and larges backwards, so if you don't like that, replace the final answer pair there with (reverse smalls,reverse larges). Let's deal with some input now:

    spL (i:input) smalls larges | i <= pivot = spL input (i:smalls) larges
                                | otherwise  = spL input smalls (i:larges)

So we pop it on the front of the smalls if it's small enough.

The reason for pushing on the front of the list is it saves us iterating through to the end of the list every time. You can always reverse to obtain the original ordering if that matters to you, like I said.

All together we get:

splitList :: (Ord a) => a -> [a] -> ([a],[a])
splitList pivot input = spL input [] [] where
    spL [] smalls larges = (smalls,larges)
    spL (i:input) smalls larges | i <= pivot = spL input (i:smalls) larges
                                | otherwise  = spL input smalls (i:larges)

Answer 4

import Data.List (partition)

splitList pivot = partition (<= pivot)

Answer 5

http://www.cs.indiana.edu/pub/techreports/TR27.pdf of 1976¹ suggests the following:

import Control.Applicative

partition3 [] p  = ZipList [[], [], []]
partition3 (x:xs) p 
   | x < p = ZipList [(x:),id,id] <*> partition3 xs p
   | x > p = ZipList [id,id,(x:)] <*> partition3 xs p
   | True  = ZipList [id,(x:),id] <*> partition3 xs p

using it, we write

splitList pivot list = (a++b, c)
   where
      [a,b,c] = getZipList $ partition3 list pivot

---

¹ as seen here.