将给定矩形拆分为n个子矩形

Question

初步评论

我正在学习Haskell.

几天前我回答的一个问题让我对Haskell的这个练习有了灵感,这给了我实验到目前为止学到的一些东西的机会,并给我留下了问题:)

问题陈述

给定宽度和高度的矩形A找到最适合A的时间的矩形B,其中最佳意味着具有最小的周长.whn

我的尝试

我开始的基本思想是生成A的子矩形集,其面积等于div (w * h) n,然后选择具有最小周长的子矩形.

以下是我提出的这个想法的三个实现; 他们是按照时间顺序排列的:我完成了第二次后得到了第三次的灵感,这是我完成第一次后得到的(好的,有一个版本0,其中我没有使用data Rectangle,只是一个元组(x, y)):

实施1

data Rectangle = Rectangle { width :: Integer,
                             height :: Integer
                           } deriving (Show)

subRectangles :: Rectangle -> Integer -> [ Rectangle ]
subRectangles r n = [ Rectangle x y | x <- [1..w ], y <- [1..h], x * y == (w * h) `div` n ]
                  where w = width r
                        h = height r

bestSubRectangle :: [ Rectangle ] -> Rectangle
bestSubRectangle [ r ] = r
bestSubRectangle (r:rs)
  | perimeter r < perimeter bestOfRest = r
  | otherwise = bestOfRest
  where bestOfRest = bestSubRectangle rs

perimeter :: Rectangle -> Integer
perimeter r = (width r) + (height r)

实施2

data Rectangle = Rectangle { width :: Integer,
                             height :: Integer
                           } deriving (Show)

subRectangles :: Rectangle -> Integer -> [ Rectangle ]
subRectangles r n = [ Rectangle x y | x <- [1..w ], y <- [1..h], x * y == (w * h) `div` n ]
                  where w = width r
                        h = height r

bestSubRectangle :: [ Rectangle ] -> Rectangle
bestSubRectangle xs = foldr smaller (last xs) xs

smaller :: Rectangle -> Rectangle -> Rectangle
smaller r1 r2 
  | perimeter r1 < perimeter r2 = r1
  | otherwise = r2

perimeter :: Rectangle -> Integer
perimeter r = (width r) + (height r)

实施3

import Data.List

data Rectangle = Rectangle { width :: Integer,
                             height :: Integer
                           } deriving (Show, Eq)

instance Ord Rectangle where
  (Rectangle w1 h1) `compare` (Rectangle w2 h2) = (w1 + h1) `compare` (w2 + h2)

subRectangles :: Rectangle -> Integer -> [ Rectangle ]
subRectangles r n = [ Rectangle x y | x <- [1..w ], y <- [1..h], x * y == (w * h) `div` n ]
                  where w = width r
                        h = height r

bestSubRectangle :: [ Rectangle ] -> Rectangle
bestSubRectangle = head . sort

问题

1. 哪种方法比较惯用？

2. 哪种方法在性能方面更好？bestSubRectangle实现3中的sort实际上取决于O(n lg n),而在实现1中,2 bestSubRectangle只需要扫描返回的数组subRectangles,从而使其成为O(n).但是我不确定Haskell laziness是否/如何工作bestSubRectangle = head . sort:将sort只生成排序数组的第一个元素,因为head只需要第一个元素(head (x:_) = x)？

3. 在实现3中,在创建Rectangle实例时,Ord我还应该定义Ord该类的其他方法吗？这是制作Rectangle实例的正确方法Ord吗？

任何进一步的改进建议/建议都非常受欢迎.

Answer 1

要回答有关 Haskell 的问题（而不是有关您选择的算法的问题）：

1. 我想说你的第二个实现是最惯用的。
2. 你是对的，这个问题只需要线性扫描，所以这sort可能比需要的更昂贵。当询问是否由于懒惰而head . sort仅计算 的结果的第一个元素时，您也提出了正确的问题sort。会的，但取决于如何sort实现，这很可能依赖于对整个列表进行排序，然后才能返回第一个元素。你应该假设确实如此。
3. 您可以从文档Ord中看出这compare已经足够了。关键词是最小完整定义：要么compare或<=。许多类型类都有相似的使用模式。您应该随意编写一个最小的实现。

关于您的代码的一些其他观察（同样，不是算法）：

• 函数调用比运算符绑定更紧密，就像在大多数语言中一样 - 只是在 Haskell 中，参数周围没有括号。因此你会写perimeter r = width r + height r
• 如果您要折叠必须至少有一个元素的列表，则可以foldr1使用bestSubRectangle xs = foldr1 smaller xs
• Ord您的for实例Rectangle与 的派生实例不一致Eq。也就是说，有些值将compare作为EQ但会返回Falsefor ==。在这种情况下，我不会尝试弯曲Rectangle的通用实例Ord来进行周长比较，而是使用smaller您在第二个实现中编写的谓词。