Есть ли у Haskell версия `foldr`? - PullRequest
Новая
       91

Есть ли у Haskell версия `foldr`?

5 голосов
/ 17 марта 2020

Страница wiki Foldr Foldl Foldl ' описывает различия между foldr и foldl. Оба списка процессов слева направо, но foldr накапливает результат справа налево, тогда как foldl - слева направо.

Страница препятствует использованию foldl в пользу более энергичной версии foldl', которая более эффективна.

Существует ли соответствующая нетерпимая версия foldr, предположительно называемая foldr'? Если да, то есть ли причина, по которой он не упоминается на вики-странице?

Ответы [ 3 ]

10 голосов
/ 17 марта 2020

Нет необходимости в foldr', так что всегда можно использовать foldr f с строгим f для достижения той же цели.

Мы могли бы определить это ... 

foldr' f a xs = foldr f' a xs
  where f' x y = seq x (seq y (f x y))

... но вместо этого проще передать строгий f в точку вызова, если это необходимо.

4 голосов
/ 17 марта 2020

Быстрый Поиск в Google показывает, что действительно существует foldr', определенный в Data.Foldable.

Я предполагаю, что причина, о которой он не упоминается на связанной странице, заключается в что это не имеет отношения к проблеме переполнения стека, обсуждаемой там. При вычислении суммы с использованием foldr (+) 0 для большого списка переполнение стека, которое может произойти, не является результатом ленивого применения оператора (+). Скорее, это происходит потому, что фундаментальная особенность правильного сгиба (строгого или ленивого) состоит в том, что наиболее глубоко вложенное приложение оператора происходит в конце списка. Для такого оператора, как (+), который требует вычисления обоих операндов для получения какого-либо результата, это означает, что либо foldr, либо foldr' должны создать O (n) стек продолжений, прежде чем добраться до конца списка где оператор (+) может начать «реальную работу».

0 голосов
/ 17 марта 2020

И foldr, и foldl' чрезвычайно полезны для списков. Ни foldl, ни foldr' часто не полезны для списков. Но в наши дни эти функции на самом деле являются методами класса Foldable, и они являются полезными в некоторых случаях. В качестве крайнего примера рассмотрим списки sno c: 

data SL a = SL a :> a | Nil
infixl 5 :>

instance Foldable SL where
  foldMap _ Nil = mempty
  foldMap f (xs :> x) = foldMap f xs <> f x

  foldl _ b Nil = b
  foldl f b (xs :> x) = f (foldl f b xs) x

  foldr' _ n Nil = n
  foldr' c n (xs :> x) =
    let n' = c x n
    in n' `seq` foldr' c n' xs

Для списков sno c действительно полезны foldl и foldr', тогда как foldr и foldl' довольно много бесполезного!

Многие контейнеры Foldable могут эффективно использовать все четыре метода. Например, Data.Set.Set, Data.Map.Map k и Data.Sequence.Seq могут быть прекрасно сложены в любом направлении. 

import Data.Sequence (Seq)
import qualified Data.Sequence as S

toForwardList :: Seq a -> [a]
toForwardList = foldr (:) []

toReverseList :: Seq a -> [a]
toReverseList = foldl (flip (:)) []

Прямое и обратное преобразования одинаково эффективны и одинаково ленивы.

...