Haskell List Осмислення та витік космосу - хешкелл, витік пам'яті, розуміння списку, монад, лінь-оцінка

Я намагаюся розібратися, як рекурсія в поєднанні зі Списком Зрозуміння / Монадічними операціями викликає витоки простору.

У мене невелика програма тестування:

module Main where
permute :: [a] -> Integer -> [[a]]
permute _ 0 = [[]]
permute xs" n = [x:xs | x <- xs", xs <- permute xs" (n-1)]
chars1 = ["0".."9"]
main = do
putStrLn $ (permute chars1 10000)!!100000000 -- Leaks
print $ [1..]!!100000000 -- Does not leak

Тепер я розумію, що функція permute можна розширити як

xs" >>= x -> (permute xs" (n-1) >>= xs -> (x:xs))

Так багато (permute xs" n) буде складено до того, як результат можна буде отримати. Я правильно розумію? Якщо так, що я можу зробити, щоб функція не просочилася?

Відповіді:

Цей код трохи дивний, тому що permute насправді не так .. добре .. перестановляйте речі, але припускаючи, що це те, що ви задумали, насправді виконує так само, як і ваш [0..] !! 10000 Наприклад, просто те, що обчислення 100-тисячного вибору - це набагато більше роботи у вашому коді!

Важливим є те, що ваш код є ледачий, ми можемо легко обчислити 1-й елемент permute [0..] 10 навіть якщо їх явно нескінченно багато.

Можливо, ви можете думати, що коли ви реально запускаєте це, потрібно зробити дуже багато часу будь-який вихід, навіть якщо ви можете сподіватися, що це будевиробляти 1-го символу ... трохи почекати .. виробляти другий символ .. трохи почекати .. і так далі. Це насправді не є "витоком" в сенсі Хаскелла, і цього сценарію неможливо уникнути. Ваш список по суті побудований з

map ("0":) (permute chars (n - 1)) ++ ... ++ map ("9":) (permute chars (n - 1))

Проблема полягає в тому, що для того, щоб знати першого символу, вам потрібно розібратися, з якого «блоку» ви будете вибирати, що передбачає обчислення довжини блоку, що передбачає оцінку permute chars (n - 1) повністю. Отже, що "у вас трапиться - ви змушуватимете кожен рекурсивний дзвінок по черзі, поки у вас не буде достатньо елементів у списку, що випливає, для оцінки дзвінка !!. Це, однак, не несподівано. Однак ви можете значно пришвидшити цей код одним досить простим трюком: перевернути його x і xs у списку осягнення.

permute :: [a] -> Integer -> [[a]]
permute _ 0 = [[]]
permute xs" n = [x:xs | xs <- permute xs" (n-1), x <- xs"]

Зверніть увагу, що збільшення обміну могло б призвести дотеорія призводить до збільшення використання пам'яті (щось не може бути GCed як тільки в цій версії), але я не в змозі придумати не абсурдно надуману програму, яка це робить.