Является ли это решение Haskell Tower of Hanoi более эффективным или просто избыточным? - PullRequest
Новая
       10

Является ли это решение Haskell Tower of Hanoi более эффективным или просто избыточным?

0 голосов
/ 08 ноября 2018

Это решение Haskell было описано как рекурсивное, но не совсем эффективное в соответствии с несколькими утверждениями, поэтому я попытался переписать его с учетом этого. Проблема описана в курсе, который доступен онлайн и домашним заданием которого была Ханойская башня .

Новое моё решение: 

type Peg = String
type Move = (Peg, Peg)

hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]

hanoi n a b c = hanoiToList n a b c []
  where
    hanoiToList 0 _ _ _ l = l
    -- hanoiToList 1 a b _ l = (a, b) : l
    hanoiToList n a b c l = hanoiToList (n-1) a c b ((a, b) : hanoiToList (n-1) c b a l)

Позвольте мне объяснить причину: если функция собирается закончить как список, то вам лучше сравнить ее с другой, которая принимает в качестве аргумента пустую, в противном случае добавьте ее после того, как она будет решена, что, я считаю, быть причиной неэффективности, что приводит к тому, что на его месте вызывается та же функция. Результат был проверен, и он верный, но я хотел знать, является ли это более эффективным или просто избыточным, учитывая предыдущее решение, с которым я связан.

РЕДАКТИРОВАТЬ: Я прокомментировал строку, которая была ненужной.

1 Ответ

0 голосов
/ 08 ноября 2018

Да, это избавляет от неэффективного копирования конструкторов (:). Это немного не-идиоматичный способ написания, но более идиоматический способ должен иметь одинаковую производительность при компиляции с оптимизацией. 

hanoi n a b c = hanoiToList n a b c []
  where
    hanoiToList 0 _ _ _ = id
    hanoiToList n a b c = hanoiToList (n-1) a c b . ((a, b) :) . hanoiToList (n-1) c b a

Это немного более идиоматический подход. Все дело в том, чтобы подчеркнуть точку зрения, что вы создаете преобразование стоимости. На практике это идентично, пока состав функции встроен и упрощен, как и ожидалось.

...