3
\$\begingroup\$

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".

\$\endgroup\$
4
\$\begingroup\$

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)]) ([],[])
\$\endgroup\$
  • \$\begingroup\$ I have to look closer at this. The "multi-fold" I'm looking for seems to be generalization of your split. \$\endgroup\$ – Landei Jul 9 '12 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.