Является ли Haskell лень элегантной альтернативой генераторам Python?

В упражнении по программированию сначала было предложено запрограммировать факториальную функцию, а затем вычислить сумму: 1! + 2! + 3! +... n! в O(n) умножениях (поэтому мы не можем напрямую использовать факториал). Я не ищу решение этой конкретной (тривиальной) проблемы, я пытаюсь изучить возможности Haskell, и эта проблема - игрушка, с которой я бы хотел играть.

Я думал, что генераторы Python могут быть хорошим решением этой проблемы. Например:

from itertools import islice
def ifact():
    i , f = 1, 1
    yield 1
    while True:
        f *= i
        i += 1
        yield f

def sum_fact(n):
    return sum(islice(ifact(),5))

Затем я попытался выяснить, было ли что-то в Haskell с аналогичным поведением, чем этот генератор, и я думал, что лень делает весь персонал без какой-либо дополнительной концепции.

Например, мы могли бы заменить myact на Python

fact = scan1 (*) [1..]

И затем решите упражнение со следующим:

sum n = foldl1 (+) (take n fact)

Интересно, действительно ли это решение эквивалентно Python относительно временной сложности и использования памяти. Я бы сказал, что решение Haskell никогда не хранит весь список, поскольку их элементы используются только один раз.

Я прав или совершенно неправ?

ИЗМЕНИТЬ: Я должен уточнить:

Prelude> foldl1 (+) (take 4 fact)
33
Prelude> :sprint fact
fact = 1 : 2 : 6 : 24 : _

Итак (моя реализация) Haskell сохраняет результат, даже если он больше не используется.

Ответ 1

Ваши примеры эквивалентны не в использовании памяти. Легко видеть, замените ли вы * на + (чтобы числа не слишком быстро увеличивались), а затем запускайте оба примера на большом n, таком как 10 ^ 7. Ваша версия Haskell будет потреблять много памяти, а python будет поддерживать ее на низком уровне.

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

Haskell будет оценивать функции лениво, но для вычисления say foldl1 (+) (take n fact) он должен будет оценить полное выражение. При больших n это разворачивается в огромное выражение так же, как и (foldl (+) 0 [0..n]). Более подробную информацию об оценке и сокращении смотрите здесь: https://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27.

Вы можете исправить свой sum n, используя foldl1' вместо foldl1, как описано в приведенной выше ссылке. Как пояснил @user2407038 в своем комментарии, вам также нужно сохранить fact local. В GHC работают с постоянной памятью:

let notfact = scanl1 (+) [1..]
let n = 20000000
let res = foldl' (+) 0 (take n notfact)

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

Ответ 2

Действительно, ленивые списки могут использоваться таким образом. Есть некоторые тонкие различия, хотя:

Списки представляют собой структуры данных. Таким образом, вы можете сохранить их после оценки, что может быть как хорошим, так и плохим (вы можете избежать перерасчета значений и рекурсивных трюков, как описано в @ChrisDrost, за счет того, что память не была выпущена).
Списки чисты. В генераторах вы можете иметь вычисления с побочными эффектами, вы не можете делать это со списками (что часто желательно).
Так как Haskell - ленивый язык, ленивость повсюду, и если вы просто конвертируете программу с императивного языка в Haskell, требования к памяти могут значительно измениться (как описывает @RomanL в своем ответе).

Но Haskell предлагает более сложные инструменты для создания шаблона генератора/потребителя. В настоящее время на эту проблему сосредоточены три библиотеки: трубы, кабелепроводы и итерации. Мой любимый conduit, он прост в использовании и сложность его типов поддерживается на низком уровне.

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

Используя трубопровод, ваш пример может быть выражен следующим образом:

import Data.Functor.Identity
import Data.Conduit
import qualified Data.Conduit.List as C

ifactC :: (Num a, Monad m) => Producer m a
ifactC = loop 1 1
  where
    loop r n = let r' = r * n
                in yield r' >> loop r' (n + 1)

sumC :: (Num a, Monad m) => Consumer a m a
sumC = C.fold (+) 0

main :: IO ()
main = (print . runIdentity) (ifactC $= C.isolate 5 $$ sumC)
-- alternatively running the pipeline in IO monad directly:
-- main = (ifactC $= C.isolate 5 $$ sumC) >>= print

Здесь мы создаем Producer (канал, который не потребляет вход), который дает факториалы бесконечно. Затем мы составляем его с помощью isolate, который гарантирует, что через него распространяется не более определенного количества значений, а затем мы составляем его с помощью Consumer, который просто суммирует значения и возвращает результат.

Ответ 3

В принципе, да: Lazy-списки Haskell очень похожи на генераторы Python, если эти генераторы были легко клонируемыми, кэшируемыми и скомпонованными. Вместо повышения StopIteration вы возвращаете [] из вашей рекурсивной функции, которая может вносить состояние в генератор.

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

facts = 1 : zipWith (*) facts [1..]

или Фибоначчи как:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

В общем, любой итеративный цикл может быть преобразован в рекурсивный алгоритм, продвигая состояние цикла к аргументам функции, а затем вызывая его рекурсивно, чтобы получить следующий цикл цикла. Генераторы такие же, но мы добавляем некоторые элементы к каждой итерации рекурсивной функции, `go ____ = (материал): go ____.

Таким образом, идеальный эквивалент:

ifact :: [Integer]
ifact = go 1 1
  where go f i = f : go (f * i) (i + 1)

sum_fact n = sum (take n ifact)

С точки зрения того, что самое быстрое, самым быстрым в Haskell, вероятно, будет "цикл цикла":

sum_fact n = go 1 1 1
  where go acc fact i
          | i <= n = go (acc + fact) (fact * i) (i + 1)
          | otherwise = acc

Тот факт, что это "хвост-рекурсивный" (вызов go не передает любые подвыборы go другой функции, такой как (+) или (*)), означает, что компилятор может его упаковать в действительно тугой цикл, и поэтому я сравниваю его с "для циклов", хотя это не настоящая идея Haskell.

Вышеупомянутый sum_fact n = sum (take n ifact) немного медленнее, чем этот, но быстрее, чем sum (take n facts), где facts определяется с помощью zipWith. Различия в скорости не очень велики, и я думаю, что в основном просто доходят до распределения памяти, которые больше не используются.