将一段Java代码翻译成Haskell

Question

我是一个可以翻译文本的有用助手。

我正在解决婴儿积木问题。我有一段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是一个对象，包含height，width，depth作为数据成员。在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新手

- user7201762

---

停止尝试编写过程式 Haskell。不要考虑变异，而是思考值的转换序列。 - Caleth

你的Java代码能正常工作吗？它里面的注释似乎在暗示着相反的情况。 :) - Alec

用语言Y翻译成语言X写作通常是最糟糕的方式之一，几乎总是会产生非常不自然的代码。请使用Haskell提供的功能来表达您的算法，而不是试图从另一种语言进行翻译。 - chi

@Caleth，实际上，我时间比较紧，而且我也没有所需的专业知识。你能帮我找一个替代方案吗？ - user7201762

Answer 1

这个问题可以通过组合非常简单的函数来找到整体解决方案，从而使其易于阅读。一种可能的策略如下：

1. 将所有可用的块作为初始塔集声明。
2. 将每个塔与每个可用块组合（如果可能）。这会导致一个新的塔集。
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：该函数根据给定的块类型（通过旋转它们），生成所有可能的块，将其转换为初始塔集（将它们包装到具有一个元素的简单列表中），并开始将初始塔集收敛为最终塔集。
• possibleBlocks：对于给定的块类型集合，该函数通过旋转它们返回所有可能的块。严格来说，应该有3！= 6种旋转方式（三个坐标的所有排列），但我们只需要考虑其中的一半，因为我们可以将交换宽度和深度的旋转视为重复。
• canStack：检查给定的块是否可以放置在另一个块上。
• expand：对于给定的塔，该函数检查所有可用块是否可以放置在塔的顶部。对于每个兼容的可以放置在顶部的块，都会创建一个新的塔。
• converge：该函数基本上为一组塔重复执行expand，直到无法再将块放置在其中之一。解决方案必须是剩余塔的最大高度。
• height：通过总结其块高度返回给定塔的高度。
• highest：对于给定的一组塔，确定最大高度。

- Michael Szvetits

---

请不要执行 == [] 操作。https://dev59.com/6W865IYBdhLWcg3wW9RE - Derek Elkins left SE

Answer 2

解决这个问题的方法（我认为）是考虑每个盒子的每个旋转方向（因此你有3n种旋转方式）。然后，根据它们底部尺寸的递增顺序对它们进行排序。问题就在于选择最长的一组可以“适合”彼此的盒子（您不需要担心选择同一个盒子两次，因为一个盒子永远不会适合自己）。这听起来很像经典的最长递增子序列问题，这表明我们将需要动态规划解决方案。我们将拥有一个长度为3n的数组，其中第i个元素表示以第i个盒子为顶部时可以制作的堆栈的最大高度。

maxHeight(i) = { height(i) + max[ maxHeight(j) ] such that
                 width(j) > width(i), depth(j) > depth(i), 0 <= j < i }

现在，让我们开始Haskell的解决方案。我假设您的输入是一个维度列表。请注意代码与我描述的解决方案密切相似 - 诀窍在于以声明方式编写事物。

import Data.List (sortOn)
import Data.Vector (fromList, (!), generate)
import Data.Ord (Down(..))

babyBlocks :: [(Int,Int,Int)] -> Int
babyBlocks blocks = maxHeights ! (3*n - 1)
  where
    -- get the number of blocks
    n = length blocks

    -- generate the `3n` blocks formed by rotating the existing blocks,
    -- sort them by their base size, and store them in a vector for
    -- fast retrieval
    sortedBlocks = fromList
                 . sortOn (\(x,y,z) -> Down (x*y))
                 . concatMap (\(x,y,z) -> [(x,y,z),(y,z,x),(z,x,y)])
                 $ blocks

    -- we'll make ourselves a couple helper functions, just so
    -- our translation of the recurrence relation looks better
    height n    = let (_,_,z) = sortedBlocks ! n in z
    width n     = let (_,y,_) = sortedBlocks ! n in y
    depth n     = let (x,_,_) = sortedBlocks ! n in x
    maxHeight n = maxHeights ! n

    -- state the dynamic programming
    maxHeights = generate (3*n) (\i ->
                   height i + maximum (0 : [ maxHeight j | j<-[0..(i-1)]
                                                         , width j > width i
                                                         , depth j > depth i ]))

你似乎遇到了最后一部分中的动态规划问题。因为 Haskell 是惰性的，所以在定义 maxHeights 时使用 maxHeight 是完全可以的，即使我不知道向量初始化的顺序是什么！

- Alec

---

请注意，以下回答并不完全正确。babyBlocks [(3,3,1), (2,2,5), (2,2,2)] 不应返回 5。 - Michael Szvetits