無理やりっぽいやり方だけど

f pred xs = do{
rs <- mapM pred xs;
let (ys, zs) = partition snd (zip xs rs);
return (map fst ys, map fst zs);
}

なら目的は果たせそう