list - 将给定的矩形拆分为 n 个子矩形

Question

初步意见

我正在学习 Haskell。

一个 question几天前我回答的这个问题给了我在 Haskell 中进行这个练习的灵感，这让我有机会尝试我迄今为止学到的一些东西，也给我留下了一些问题:)

问题陈述

给定一个矩形 一个 宽度 w和高度 h找到最佳矩形 乙适合 n 内的次数一个 ，其中最好的意思是具有最小的周长。

我的尝试

我从生成 的子矩形集的基本思想开始。一个 面积等于 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

问题

哪种方法更惯用？

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

在实现 3 中，当制作 Rectangle Ord 的一个实例我还应该定义Ord 的其他方法吗？类(class)？这是制作Rectangle的正确方法吗？ Ord 的一个实例?

非常欢迎任何进一步的改进建议/建议。

Answer 1

要回答您关于 Haskell 的问题(而不是关于您选择的算法):

我想说你的第二个实现是最惯用的。

你是对的，这个问题只需要线性扫描，所以 sort可能比需要的贵。当你问是否由于懒惰，head . sort 时，你也在问正确的问题。将仅计算 sort 结果的第一个元素.它会，但取决于 sort已实现，这很可能依赖于在返回第一个元素之前对整个列表进行排序。你应该假设它确实如此。

您可以从 documentation for Ord 中得知那compare足够了。关键词是最小完整定义:compare或 <= .许多类型类具有相似的使用模式。您应该随意编写他们所做的最小实现。

关于您的代码的其他一些观察结果(同样，不是算法):

与大多数语言一样，函数调用比运算符绑定(bind)得更紧密——只是在 Haskell 中，参数周围没有括号。因此你会写perimeter r = width r + height r

如果要折叠必须至少包含一个元素的列表，可以使用 foldr1如 bestSubRectangle xs = foldr1 smaller xs

您的 Ord 实例对于 Rectangle不同意 Eq 的派生实例.也就是说，有些值将 compare如EQ但会返回 False对于 == .在这种情况下，我不会尝试弯曲 Rectangle的 Ord 的通用实例出于周长比较的目的，而是使用 smaller您在第二个实现中编写的谓词。