Translating a piece of Java code to Haskell

Question

I am solving the Baby Blocks problem. I have a peice of java code that I want to translate to Haskell:

Java:

for (int i = 1; i <optHeight.length ; i++) {
    int maxHeightIndex = 0;
        for (int j = i-1; j >=0 ; j--) {
            // Need help from here
            if(boxes[j].width>boxes[i-1].width && boxes[j].depth>boxes[i-1].depth) {
                if(optHeight[maxHeightIndex]<optHeight[j+1]) { <-- How do I write this condition
                    maxHeightIndex = j+1;
                }
            }
        }
        optHeight[i]=optHeight[maxHeightIndex] + boxes[i-1].height;
}

where optHeight is a 1-D array and boxes is an object consiting of height, width, depth as data members. In Haskell, it is just a list of list. Due to lack of mutable arrays / variables, I am totally helpless.

Haskell:

b list = do
 forM_ [1..length list] $ \i -> do
  let maxHeight = 0
  forM_ [0..(i-1)] $ \j  -> do
   if list!!j!!1 > list!!i-1!!1 && list!!j!!2 > list !!j!!2 then
    maxHeight = j + 1

PS: I am totally a beginner in Haskell

Answer 1

This problem can be solved in a very readable way by composing very simple functions to find the overall solution. A possible strategy is as follows:

1. Take all the available blocks and declare them as an initial set of towers.
2. Combine each tower with each available block (if possible). This results in a new set of towers.
3. Repeat step 2 until the set of towers does not change anymore.
4. Extract the tower of the set which is the highest.

The corresponding code is as follows (explanation below):

type Block = (Int,Int,Int)
type Tower = [Block]

babyBlocks :: [Block] -> Int
babyBlocks blocks = highest $ converge allBlocks initialTowers
    where allBlocks = possibleBlocks blocks
          initialTowers = map (:[]) allBlocks

possibleBlocks :: [Block] -> [Block]
possibleBlocks = concatMap (\(w,d,h) -> [(w,d,h),(w,h,d),(d,h,w)])

canStack :: Block -> Block -> Bool
canStack (w1,d1,_) (w2,d2,_) = w2 < w1 && d2 < d1 || w2 < d1 && d2 < w1

expand :: Tower -> [Block] -> [Tower]
expand tower@(top:_) = map (:tower) . filter (canStack top)

converge :: [Block] -> [Tower] -> [Tower]
converge blocks towers | null newTowers = towers
                       | otherwise = converge blocks newTowers
    where newTowers = concatMap (flip expand blocks) towers

height :: Tower -> Int
height = sum . map (\(_,_,h) -> h)

highest :: [Tower] -> Int
highest = maximum . map height

• babyBlocks : This function generates all possible blocks for the given block types (by rotating them), converts them into an initial tower set (by wrapping them into simple list with one element) and starts the convergence of the initial tower set into a final tower set.
• possibleBlocks : For a given set of block types, this function returns all possible blocks by rotating them. Strictly, there should be 3! = 6 rotations (all permutations of the three coordinates), but we only need to consider half of them because we can treat rotations with swapped widths and depths as duplicates.
• canStack : Checks if a given block can be placed onto another block.
• expand : For a given tower, the function checks all the available blocks if they can be put on the top of the tower. A new tower is created for each compatible block that can be put on top.
• converge : This function essentially repeats expand for a set of towers until no more block can be put on one of them. The solution must be the maximum height of the remaining towers.
• height : Returns the height of a given tower by summing up its block heights.
• highest : For a given set of towers, identifies the maximum height.