java - 将一段 Java 代码翻译为 Haskell

Question

我正在解决Baby Blocks问题。我有一段 java 代码，我想将其转换为 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;
}

其中optHeight是一个一维数组，boxes是一个由高度、宽度、深度作为数据成员组成的对象。在 Haskell 中，它只是一个列表的列表。由于缺乏可变数组/变量，我完全无能为力。

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:我完全是 Haskell 的初学者

Answer 1

这个问题可以通过编写非常简单的函数来找到整体解决方案，以一种非常可读的方式来解决。一种可能的策略如下:

1. 获取所有可用 block 并将它们声明为一组初始塔。
2. 将每个塔与每个可用 block 组合起来(如果可能)。这会产生一组新的塔楼。
3. 重复步骤 2，直到塔组不再发生变化。
4. 提取集合中最高的塔。

对应的代码如下(解释如下):

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 :该函数为给定的 block 类型生成所有可能的 block (通过旋转它们)，将它们转换为初始塔集(通过将它们包装成带有一个元素的简单列表)并开始将初始塔集收敛为最终塔集.
• possibleBlocks :对于给定的一组 block 类型，此函数通过旋转它们来返回所有可能的 block 。严格来说应该有3! = 6旋转(三个坐标的所有排列)，但我们只需要考虑其中的一半，因为我们可以将交换宽度和深度的旋转视为重复。
• canStack :检查给定的 block 是否可以放置到另一个 block 上。
• expand :对于给定的塔，该函数检查所有可用的 block 是否可以放置在塔的顶部。为每个可以放在顶部的兼容 block 创建一个新塔。
• converge :这个函数本质上是重复expand对于一组塔，直到不能再在其中一个塔上放置更多的方 block 为止。解决方案必须是剩余塔的最大高度。
• height :通过总结给定塔的 block 高度来返回其高度。
• highest :对于给定的一组塔，确定最大高度。