Предварительные замечания

Я изучаю Haskell.

вопрос , на который я ответил несколько дней назад, вдохновил меня на это упражнение на Haskell, которое дало возможность поэкспериментировать с некоторыми вещами, которым я научился до сих пор, а также оставило меня с вопросами :)

Постановка задачи

Для прямоугольника A шириной w и высотой h найдите лучший прямоугольник B , который соответствует n раз в пределах A , где best означает наименьший периметр.

Моя попытка

Я начал с основной идеи создания набора подпрямоугольников 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 на bestSubRectangle = head. sort : будет sort создать только первый элемент отсортированного массива, поскольку head требует только первого элемента ( head (x: _) = x) ?

3. В реализации 3, при создании Rectangle экземпляром Ord должен ли я также определять другие методы класса Ord ? Правильно ли это сделать Rectangle экземпляром Ord ?

Мы приветствуем любые дальнейшие предложения / рекомендации по улучшению.