How to avoid explicit recursion if you have to collect multiple “branches”?

Question

The question was, which is the biggest product you can make from the digits of 1 to 9 (which is 9642*87531, BTW). It is pretty clear that one number starts with 9 and the other with 8, and that you need to append the remaining digits in descending order to one or the other number.

buildList x y [] acc = (x,y):acc 
buildList x y (z:zs) acc = buildList (10*x+z) y zs (buildList x (10*y + z) zs acc)

list = buildList 9 8 [7,6,5,4,3,2,1] []

Sorting it by descending products, and taking the beginning of the list:

import Data.List
import Data.Function
result = take 10 $ sortBy (compare `on` (negate.uncurry (*))) list

I'm not satisfied with my solution for buildList, which uses explicit recursion. I'd like to have something like a fold, just not linear but with different "branches".

Answer 1

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)]) ([],[])