Когда использовать Foldr с продолжением в качестве функции накопления? - PullRequest
Новая
       49

Когда использовать Foldr с продолжением в качестве функции накопления?

0 голосов
/ 08 июня 2018

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

Большинство людей уже видели эту технику раньше, когда использовали foldr для определения foldl: 

myFoldl :: forall a b. (b -> a -> b) -> b -> [a] -> b
myFoldl accum nil as = foldr f id as nil
  where
    f :: a -> (b -> b) -> b -> b
    f a continuation b = continuation $ accum b a

Здесь тип функции объединения f не просто a -> b -> b, как обычно, но a -> (b -> b) -> b -> b.Требуется не только a и b, но и продолжение (b -> b), которое нам нужно передать b, чтобы получить последний b.

I в последнее время.видел пример использования этого трюка в книге Параллельное и параллельное программирование на Haskell . Здесь - ссылка на исходный код примера, использующего этот трюк. Здесь - ссылка на главу книги, объясняющую этот пример.

Я позволил себе упростить упрощение исходного кода до аналогичного (но более короткого) примера.Ниже приведена функция, которая принимает список строк, распечатывает, превышает ли длина каждой строки пять, а затем печатает полный список только строк, длина которых превышает пять: 

import Text.Printf

stringsOver5 :: [String] -> IO ()
stringsOver5 strings = foldr f (print . reverse) strings []
  where
    f :: String -> ([String] -> IO ()) -> [String] -> IO ()
    f str continuation strs = do
      let isGreaterThan5 = length str > 5
      printf "Working on \"%s\", greater than 5? %s\n" str (show isGreaterThan5)
      if isGreaterThan5
        then continuation $ str : strs
        else continuation strs

Вотпример использования его из GHCi: 

> stringsOver5 ["subdirectory", "bye", "cat", "function"]
Working on "subdirectory", greater than 5? True
Working on "bye", greater than 5? False
Working on "cat", greater than 5? False
Working on "function", greater than 5? True
["subdirectory","function"]

Как и в примере myFoldl, вы можете видеть, что функция объединения f использует тот же трюк.

Однако этомне пришло в голову, что эту stringsOver5 функцию, вероятно, можно написать без этого трюка: 

stringsOver5PlainFoldr :: [String] -> IO ()
stringsOver5PlainFoldr strings = foldr f (pure []) strings >>= print
  where
    f :: String -> IO [String] -> IO [String]
    f str ioStrs = do
      let isGreaterThan5 = length str > 5
      printf "Working on \"%s\", greater than 5? %s\n" str (show isGreaterThan5)
      if isGreaterThan5
        then fmap (str :) ioStrs
        else ioStrs

(хотя, возможно, вы могли бы сделать аргумент, что IO [String] является продолжением ?)

У меня есть два вопроса по этому поводу:

  • Совершенно необходимо ли использовать этот прием для передачи продолжения в foldr вместо использования foldr снормальное значение как аккумулятор?Есть ли пример функции, которая абсолютно не может быть написана с использованием foldr с нормальным значением?(Помимо foldl и подобных функций, конечно.)
  • Когда я захочу использовать этот трюк в своем собственном коде?Есть ли какой-нибудь пример функции, которую можно значительно упростить с помощью этого трюка?
  • Есть ли какие-либо соображения производительности, которые следует учитывать при использовании этого трюка?(Или, ну, когда не использует этот трюк?)

1 Ответ

0 голосов
/ 08 июня 2018

У меня есть два вопроса по этому поводу:

Для некоторого большого значения «два»: -P

  • Это абсолютно необходимо?использовать этот трюк передачи продолжения в Foldr?Есть ли пример функции, которая абсолютно не может быть написана без этого трюка?(Кроме свёрток и подобных функций, конечно.)

Нет, никогда.Каждый вызов foldr всегда можно заменить явной рекурсией.

Следует использовать foldr и другие известные библиотечные функции, когда они делают код проще.Если этого не происходит, не следует вводить код в чистую форму, чтобы он соответствовал шаблону foldr.

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

Сравнитеваш код с этим, например: 

stringsOver5 :: [String] -> IO ()
stringsOver5 strings = go strings []
  where
  go :: [String] -> [String] -> IO ()
  go []     acc = print (reverse acc)
  go (s:ss) acc = do
      let isGreaterThan5 = length str > 5
      printf "Working on \"%s\", greater than 5? %s\n" str (show isGreaterThan5)
      if isGreaterThan5
        then go ss (s:acc)
        else go ss acc
  • Когда я хотел бы использовать этот трюк в моем собственном коде?Есть ли какой-нибудь пример функции, которую можно значительно упростить с помощью этого трюка?

По моему скромному мнению, почти никогда.

Лично я нахожу "звонить foldr с четырьмя (или более) аргументами "в большинстве случаев быть анти-паттерном.Это потому, что он не так короток, как использование явной рекурсии, и потенциально может быть гораздо менее читабельным.

Я бы сказал, что эта «идиома» весьма озадачивает любого Хаскеллера, который ее раньше не видел.Это своего рода приобретенный вкус, так сказать.

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

foldr (.) id listOfDLists []

прекрасно, даже если последний [] может поначалу озадачивать.

  • Есть ли какие-либо соображения производительности, которые следует учитывать при использовании этого трюка?(Или, если не использовать этот трюк?)

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

Возможно, использование foldr может помочь GHC запустить некоторые правила оптимизации сворачивания / построения, но я не уверен в необходимости делать это при использовании продолжений.

...