Переведите поток управления с помощью break-s / continue-s в haskell

Question

Рассмотрим следующий императивный код, который находит самый большой палиндром среди произведений трехзначных чисел (да, это одна из первых задач с сайта «Проект [выдающегося математика XVIII века]»):

curmax = 0
for i in range(999,100):
for j in range(999,100):
    if ((i*j) < curmax): break
    if (pal(i*j)):
        curmax = i*j
        break
print curmax

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

Моя версия

maxpal i curmax
    | i < 100 = curmax
    | otherwise = maxpal (i-1) (innerloop 999)
    where 
        innerloop j
            | (j < 100) || (p < curmax) = curmax
            | pal p = p
            | otherwise = innerloop (j-1)
            where p = i*j
main = print $ maxpal 999 0

но похоже, что мы все еще в безобразном уродливом городе.

Так что вы могли бы посоветовать, чтоЕсть ли подходы к решению таких случаев в стиле FP?

Answer 1

Аналогичный ответ Даниэля и Сеппка:

Ленивое функциональное программирование позволяет писать программы гораздо более модульно, чем вы видите в императивном потоке управления, подобном тому, который задан в вашем вопросе.Например, сформируйте список факторов 999 ... 100, затем все продукты, затем отфильтруйте, чтобы сохранить только палиндромы, а затем вычислите максимум.Благодаря лень эти промежуточные списки будут создаваться только по мере необходимости и будут постепенно перерабатываться.

Дополнительные сведения и примеры см. В классической статье Джона Хьюза ПочемуВопросы функционального программирования .

maxpal :: Int
maxpal = maximum [i*j | i <- factors, j <- factors, pal (i*j) ]

factors :: [Int]
factors = [999,998..100]

pal :: Show a => a -> Bool
pal = palL . show

palL :: (Eq a) => [a] -> Bool
palL xs = xs == reverse xs

Answer 2

Если мы покончим со всей оптимизацией и просто умножим все комбинации чисел между 100 и 999, отфильтруем неполиндромы и возьмем максимум этого, мы можем записать функцию очень кратко, как:

maximum $ filter pal [x*y | x <- [100..999], y <- [100..999]]

Конечно, это в основном наименее эффективный способ сделать это, но, поскольку числа относительно невелики, это все равно заканчивается на полсекунде на моей машине.

Однако если мы хотим что-то, чтоБолее того, алгоритмически, в соответствии с вашим решением Python, мы можем сделать это следующим образом:

import Data.Maybe
import Data.List

maxpal i curmax
    | i < 100 = curmax
    | otherwise = maxpal (i-1) newmax
    where newmax = fromMaybe curmax (find pal bigger)
          bigger = takeWhile (> curmax) (map (*i) [999, 998 ..])

Здесь внешний цикл в основном такой же, как в вашем решении, но мы заменили внутренний цикл, используя вместо этого функции списка.

Мы используем map (*i) [999, 998, ...] для создания продукта i*j для каждого j с обратным отсчетом от 999.Используя takeWhile, мы говорим, что список должен остановиться, когда значение не превышает curmax.

Затем мы используем find, чтобы увидеть, является ли какой-либо элемент в этом списке палиндромом.Если это так, первый палиндром в списке - это наш новый максимум.Если это не так, мы сохраняем наш старый максимум.(find возвращает Maybe, а fromMaybe принимает значение по умолчанию и Maybe и возвращает значение из Maybe или значение по умолчанию, если в Maybe нет значения)

Answer 3

Итак, думая функционально, вы должны искать способы разбить свою проблему не на циклы и шаги, а на функции.

Итак, если бы у нас была функция maxWhere f xs, которая вернула бы наибольшее значение x длячто f x верно, мы могли бы написать:

maxpal = maxWhere pal [x * y | x <- [999,998..100], y <- [999,998..100]]

Наивная реализация maxWhere равна

maxWhere f xs = maximum $ filter f xs

, но это плохо, если f дороже, чем сравнение, поскольку мыЯ буду звонить больше, чем в оригинале.Мы можем использовать сгиб, чтобы объединить фильтр и максимум в один проход и получить то же поведение, что и императивный код.

maxWhere f xs = foldl' r 0 xs
    where r a x
       | x > a     = if f x then x else a
       | otherwise = a

Использование нуля в качестве магического малого числа здесь ужасно, но работает вэтот случай.

(я действительно хочу записать этот список номеров кандидатов (*) <$> [999,998..100] <*> [999,998..100], но это может привести к ненужным усложнениям здесь.)

Answer 4

Здесь нет универсального ответа.Но давайте рассмотрим этот конкретный пример:

Сначала рассмотрим внешний цикл: мы всегда выполняем полный диапазон, и нам важен только конечный максимум, поэтому это достаточно просто:

outerLoop = foldl innerLoop 0 [999,998..100]

Во внутреннем цикле у нас есть некоторое значение i и текущий максимум.Теперь мы заботимся только о диапазоне, где i * j больше текущего максимума:

innerLoop curmax i = foldr checkMax curmax [999*i, 998*i .. curmax]

В основной логике мы получаем значение для i * j, которое, как мы знаем, всегда будет больше или равнотекущий максимум, так что все, что нужно, это проверить следующее значение, чтобы увидеть, является ли это палиндромом: если это так, мы закончили, потому что последовательность уменьшается.Если нет, отложите решение:

checkMax ij defer = if pal ij then ij else defer

Answer 5

На мой взгляд, диапазон соответствует списку. Например:

f = [999,998..100]

Теперь f определяется как последовательность чисел от 999 до 100.

for циклы соответствуют различным функциональным концепциям, в зависимости от того, что вы делаете в каждой итерации. Иногда map является подходящим аналогом, иногда fold, иногда что-то еще. Часто это комбинация вещей. В этом случае вы эффективно объединяете два списка. Одним из способов сделать это в Haskell является понимание списка:

g = [(x * y) | x <- f , y <- f]

Здесь g представляет собой список произведений каждого элемента ранее определенной последовательности в сочетании с самим собой. Другими словами, в значительной степени то, что у вас происходит в цикле for.

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

Answer 6

этот вид цикла легко поддается пониманию списка, например:

maximum [x*y | x <- [999..100], y <- [999..100],isPalindrome (x*y)]

Где мы можем написать isPalindrome, как это:

isPalindrome x = xs == reverse xs
  where xs = show x

Это действительно достаточно быстро, хотя и немного неприлично, поэтому сначала заметим, что мы проверяем цифры дважды. Допустим, a * b - самый большой палиндром, тогда мы проверим как случай, когда x == a, y==b, так и x==b, y==a. Итак, сначала мы остановим это, ограничив числа, которые мы ищем, только теми случаями, когда x> = y, например:

maximum [x*y | x <- [999..100], y <- [x..100],isPalindrome (x*y)]

Это сокращает числа для проверки пополам.

В своем решении на python вы также связываете y ниже наибольшим из найденных нами значений, деленным на текущее x (x*y => curmax), также вы никогда не будете искать за пределами первого найденного y (прерывая внутренний цикл при обновлении curmax ). Мы можем сократить поиск дальше, не продолжая, если первый проверяемый элемент (x в квадрате) меньше нашего текущего ответа, так как все последующие проверки меньше, но это выходит за рамки того, что выглядит хорошо в понимании списка, поэтому мы переместим наш поиск в это собственная функция:

import Data.List(find)
import Data.Maybe(isNothing,fromJust)

search x curr 
   | x * x < curr                   = curr
   | isNothing maypal || pal < curr = search (x - 1) curr 
   | otherwise                      = search (x - 1) pal 
   where maypal = find isPalindrome [x * x, (x - 1) * x .. curr]
         pal    = fromJust maypal

Стоит заметить, что наше ограничение, (x*x) < curr, на самом деле просто означает, что отныне [x*x,(x-1)*x..curr] будет пустым. Как вы можете видеть, все границы, которые были установлены разрывами в вашем коде Python, помещаются в одну итерацию по x (с использованием рекурсии) и находят список значений x * y. Это может показаться нехорошо, но мне кажется, что нужно более четко изложить ограничения, которые мы налагаем на x и y.

Запустив его, мы получим:

*Main> search 999 0
906609

Оказывается, что остановка, когда x * x < curr - это действительно хорошая идея, поскольку квадратный корень из 906609 равен 952 ...

Answer 7

Г. Побитый sepp2k, но я отвечу на ваш общий вопрос:

Временные переменные также могут быть выражены с помощью монады состояния или монады ST, если у вас их много. FP часто побеждает в краткости и ясности, но в некоторых случаях это не так, например. когда есть несколько локальных переменных для жонглирования.

Лень может эмулировать множество разрывов, но при работе с IO вам обычно приходится использовать явную рекурсию. Однако пакет List (из Hackage) довольно умен, позволяя вам писать циклы ввода-вывода в функциональном стиле.

Answer 8

Я думаю, что вы можете делать то, что хотите, используя две взаимно рекурсивные функции.

Вот гораздо более простой пример (взят из учебника по ATS ):

implement main (argc, argv) = let
  fun loop1 (i: int): void =
    if i <= 9 then loop2 (i, i) else ()

  and loop2  (i: int, j: int): void =
    if j <= 9 then begin
      if i < j then begin
        print ", ";
        print "("; print i; print ", "; print j; print ")";
        loop2 (i, j+1)
      end
    end else begin
      print_newline ();
      loop1 (i+1)
    end
  in
    loop1 0
  end

Код, написанный выше, очень похож на то, что вы написали бы на C (взято с той же страницы):

int main (int argc, char * argv []) {int i, j;

for (i = 0; i <= 9; i += 1) {
  for (j = i; j <= 9; j += 1) {
    if (i < j) printf (", ") ; printf ("(%i, %i)", i, j) ;
  } /* for */
  printf ("\n") ;
} /* for */

return 0 ;

}

Как видите, вложенные циклы становятся взаимно рекурсивными функциями;и изменчивые переменные i и j становятся переменными индукции.loop1 соответствует внешнему циклу, а loop2 - внутреннему циклу.

Answer 9

Как отметил Стивен Тетли в своем комментарии, в FP вы можете использовать стиль передачи продолжения для обработки сложного потока управления (Cont монада плюс ее callCC, что как-то похоже на break.... или даже goto - злоупотребление CPS может привести к довольно непонятному коду - см. мой пример ниже):

import Control.Monad.Cont

pal n = sn == reverse sn
    where sn = show n

range = [99999,99998..10000]

mfoldM a r f = foldM f a r  

curmaxm = (`runCont` id) $ mfoldM 0 range $ \m i ->
            callCC $ \break ->
                mfoldM m range $ \m j -> do
                  let ij = i*j
                  if ij < m
                     then break m
                     else return $
                          if pal ij then ij else m

Два mfoldM (просто стандартный foldM с переставленными аргументами) соответствуют двум цикламв исходном примере break аргумент-функция используется во "внутреннем цикле", чтобы выйти из него один раз (i * j> current max), когда нарушается условие (возвращая текущий максимум в результате этого "внутреннего цикла").Здесь нам нужно выйти из одного «уровня цикла», так что callCC здесь явно излишним.

Та же логика может быть реализована и с find (+ лень Haskell):

import Data.List
import Data.Maybe
import Control.Monad

curmax = fromJust $ foldM it 0 range
    where 
      it m i = (find pal . takeWhile (>m) . map (*i) $ range) `mplus` return m

find pal здесь возвращает либо первое число палиндрома (которое также будет удовлетворять условию (> m) в takeWhile), либо Nothing (ноль MonadPlus) и после mplus (или Alternatice. <|>) itвозвращает либо новый максимальный палиндром, либо предыдущий максимум (return m).Поскольку find прекращает поиск, как только найден первый удовлетворяющий элемент, этот код ведет себя точно так же, как и его императивный curmax аналог.Обе версии работают для диапазона [99999..10000] за 0,5 секунды.

Обновление: Просто для удовольствия: тот же подход, но с использованием StateT Integer (Cont Integer) () - Cont для выхода из «цикла» иСостояние, чтобы передать максимальный палиндром (плюс возможность использовать forM_ и when).Одинаковая эффективность:

import Control.Monad.Cont
import Control.Monad.State.Strict

solcs = runCont (execStateT comp 0) id
    where   
      comp = forM_ range $ \i -> callCC $ \break ->
                forM_ range $ \j -> do
                  let ij = i*j
                  m <- get
                  when (ij < m) (break ())
                  when (pal ij) (put ij)