Consideremos la siguiente función
split:: (Ord a)=> a->[a]->([a],[a])
split x l = ( [y |y <- l, y <=x] , [y|y <- l, y > x])
Defina una versión de esta función que trabaje en exactamente una sola pasada a la lista “l“.
Habría varias formas. Una podría ser mediante dobleces:
split :: Ord a => a -> [a] -> ([a],[a])
split x xs = foldl aux ([],[]) xs
where aux (ys,zs) w | w <= x = (w:ys, zs)
| otherwise = (ys, w:zs)
Más clara queda definida por recursividad:
split :: Ord a => a -> [a] -> ([a],[a])
split _ [] = ([],[])
split x (y:ys) | y <= x = (y:zs, ws)
| otherwise = (zs, y:ws)
where zs, ws = split x ys
Incluso una versión compacta con aplicativos, más matemática:
split :: Ord a => a -> [a] -> ([a],[a])
split x = (,) <$> filter (<= x) <*> filter (> x)
l
, o sea, se recorre dos veces de principio a fin. Tienes que idear un modo de que la lista sólo sea recorrida una vez de principio a fin. Añade a la pregunta el código que hayas intentado y miraremos cómo poder ayudarte.