Как hGetContents достигает эффективности памяти?

Question

Я хочу добавить Haskell к своему набору инструментов, так что я пробираюсь через Real World Haskell.

В главе "Вход и выход", в разделеhGetContentsЯ наткнулся на этот пример:

import System.IO
import Data.Char(toUpper)

main :: IO ()
main = do 
    inh <- openFile "input.txt" ReadMode
    outh <- openFile "output.txt" WriteMode
    inpStr <- hGetContents inh
    let result = processData inpStr
    hPutStr outh result
    hClose inh
    hClose outh

processData :: String -> String
processData = map toUpper

После этого примера кода авторы продолжают:

Заметить, что hGetContents занимался всем чтением для нас. Кроме того, взгляните на processData, Это чистая функция, поскольку она не имеет побочных эффектов и всегда возвращает один и тот же результат при каждом вызове. Ему не нужно знать -и нет никакого способа сказать- что его ввод лениво читается из файла в этом случае. Он может прекрасно работать с 20-символьным литералом или 500 ГБ данных на диске. (NB Акцент мой)

Мой вопрос: как hGetContents или его результирующие значения достигают этой эффективности памяти без - в этом примере - processData "быть способным сказать" и при этом поддерживать все преимущества, которые дает чистый код (т.е. processData) конкретно запоминание?

<- hGetContents inh возвращает строку так inpStr привязан к значению типа Stringэто именно тот тип, который processData принимает. Но если я правильно понимаю авторов Real World Haskell, то эта строка не совсем похожа на другие строки, в том смысле, что она не полностью загружена в память (или не полностью оценена, если существует такая вещь, как строки, не полностью оцененные)..) к моменту звонка processData,

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

Есть ли экземпляры типа String что каждый ведет себя по-разному, но его нельзя отличить на этом уровне абстракции?

Answer 1

String вернулся hGetContents ничем не отличается от любой другой строки Haskell. Как правило, данные на Haskell не оцениваются полностью, если только программист не предпринял дополнительных шагов для их проверки (например, seq, deepseq, взрыва моделей).

Строки определены как (по существу)

data List a = Nil | Cons a (List a) -- Nil === [], Cons === :
type String = List Char

Это означает, что строка либо пуста, либо один символ (голова) и другая строка (хвост). Из-за лени хвост может не существовать в памяти и даже может быть бесконечным. После обработки Stringпрограмма на Haskell обычно проверяет, Nil или же Cons, затем ответвляйтесь и продолжайте по мере необходимости. Если функции не нужно оценивать хвост, она не будет. Этой функции, например, нужно только проверить начальный конструктор:

safeHead :: String -> Maybe Char
safeHead [] = Nothing
safeHead (x:_) = Just x

Это совершенно законная строка

allA's = repeat 'a' :: String

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

Однако твоя интуиция о том, что происходит что-то странное, верна. hGetContents реализуется с помощью специальной функции unsafeInterleaveIO, которая по сути является подключением компилятора к IO поведение. Чем меньше об этом сказано, тем лучше.

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