Here is a quick try to implement your algorithm using 'foldr'. I did not check in depth whether my solution is correct.
I have divided the problem into parts. First we define a function that takes a list and splits the list into pairs of partitions where the order of elements is preserved.
split :: [a] -> [([a],[a])]
split [] = [([],[])]
split (x:xs) = concatMap (\(fst,snd) -> [(x:fst,snd), (fst,x:snd)]) (split xs)
Employing this definition we can define the list of tuples of decimals.
combinations :: [([Int],[Int])]
combinations = map (\(fst,snd) -> (9:fst,8:snd)) (split [7,6..1])
To transform these lists of decimals into numbers we use the following transformation.
toDeci :: [Int] -> Int
toDeci = foldl (\acc x -> x + 10 * acc) 0
Combining these functions we can redefine list as follows.
list :: [(Int,Int)]
list = map (\(fst,snd) -> (toDeci fst,toDeci snd)) combinations
Now we can define split by using foldr.
We can probably improve the code by using predefined functions like the arrow function (***).
Edit: You can generalize split by using the list monad. First we defined split using foldr as follows.
foldr (\x -> concatMap (\(fst,snd) -> [(x:fst,snd), (fst,x:snd)])) [([],[])]
Now we can observe that the neutral element is return ([],[]) in the list monad and concatMap is the implementation of (>>=). That is, we can define split as follows.
foldr (\x xs -> xs >>= (\(fst,snd) -> [(x:fst,snd), (fst,x:snd)])) (return ([],[]))
This implementation can be shortened by using the predefined function foldM from Control.Monad.
foldM (\(fst,snd) x -> [(x:fst,snd), (fst,x:snd)]) ([],[])
