Haskell: 동일한 게으른 리스트에 대해 여러 폴드를 메모리에 유지하지 않고 실행할 수 있을까요?

저의 컨텍스트는 생물정보학이며 특히 차세대 시퀀싱입니다. 하지만 문제는 일반적이므로 예시로 로그 파일을 사용하겠습니다.

이 파일은 매우 큽니다 (기가바이트 단위로 압축되어 있으므로 메모리에 맞지 않습니다) 하지만 파싱하기 쉽습니다 (각 줄은 항목입니다) 따라서 다음과 같이 간단하게 작성할 수 있습니다:

parse :: Lazy.ByteString -> [LogEntry]

이제 로그 파일에서 계산하려는 많은 통계가 있습니다. 가장 쉬운 방법은 다음과 같이 별도의 함수를 작성하는 것입니다:

totalEntries = length
nrBots = sum . map fromEnum . map isBotEntry
averageTimeOfDay = histogram . map extractHour

이 모든 함수들은 foldl' k z . map f 형태입니다.

문제는 가장 자연스러운 방법으로 이러한 함수를 사용하려고 하면 다음과 같습니다.

main = do
    입력 <- 게으른.readFile input.txt
    let 로그입력 = analysis 입력
        총입력 = 총입력수 로그입력
        봇수 = 봇수 로그입력
        평균시간 = 하루평균시간 로그입력
    출력 총입력
    출력 봇수
    출력 평균시간

이렇게 하면 전체 리스트를 메모리에 할당하게 되어, 원하는 결과가 아닙니다. 접는 동안 셀들이 가비지 컬렉션될 수 있도록 동기적으로 계산되어야 합니다. 단일 통계만을 계산한다면 이런 일이 벌어집니다.

이를 위해 단일 큰 함수를 작성할 수 있지만, 그것은 조립 가능하지 않은 코드입니다.

또 다른 방법으로, 제가 하고 있던 것처럼 각 통과마다 별도로 실행할 수 있지만, 이는 파일을 매번 다시 로드하고 압축을 해제합니다.

답변 1

{-# LANGUAGE GADTs, BangPatterns #-}
import Data.List (foldl', unfoldr)
import Control.Applicative 
import qualified Data.ByteString.Lazy.Char8 as B
main = fmap readInts (B.readFile int.txt) >>= print . 함수 allThree
  where allThree = (,,) <$> 함수 length_ <*> 함수 sum_ <*> 함수 maximum_
data Fold b c where  F ::  (a -> b -> a) -> a -> (a -> c) -> Fold b c
data Pair a b = P !a !b
instance Functor (Fold b) where  fmap f (F op x g) = F op x (f . g)
instance Applicative (Fold b) where
  pure c = F const () (const c)
  (F f x c) <*> (F g y c') = F (comb f g) (P x y) (c *** c')
    where comb f g (P a a') b = P (f a b) (g a' b)
          (***) f g (P x y) = f x ( g y)
fold :: Fold b c -> [b] -> c
fold (F f x c) bs = c $ (foldl' f x bs)
sum_, product_ :: Num a => Fold a a
length_ :: Fold a Int
sum_     = F (+) 0 id
product_ = F (*) 1 id
length_  = F (const . (+1)) 0 id
maximum_ = F max 0 id
readInts  = unfoldr $ \bs -> case B.readInt bs of
  Nothing      -> Nothing
  Just (n,bs2) -> if not (B.null bs2) then Just (n,B.tail bs2) 
                                      else Just (n,B.empty)

편집: 상자가 없는 형식과 2G 파일에서 파생된 상자 없는 벡터를 처리해야하므로, 이 경우에는 메모리에 맞는 상자 없는 벡터가 두 배 빠르고 다소 더 잘 작동합니다. Data.Vector.Uboxed에 대한 명확한 다시 지정이 제공되면 http://hpaste.org/69270 이 당연히 LogEntry와 같은 형식이 있는 경우에는 관련이 없습니다. 그러나 '접기' 유형과 접기 '곱셈'은 수정없이 순차적 유형에 대해 일반화됩니다. 따라서 Char 또는 Word8에 대한 작업에 연결된 Fold는 동시에 바이트 스트링을 직접적으로 접을 수 있습니다. 먼저 각 바이트 스트링 모듈의 foldl'를 사용하여 fold를 다시 지정하여 foldB를 정의해야합니다. 그러나 Fold와 Fold의 곱은 여전히 목록이나 벡터를 접는 것과 동일합니다. Char 또는 Word8의에 대해서

답변 2

하스켈: 리스트를 메모리에 유지하지 않고 동일한 게으른 리스트에 여러 폴드를 수행할 수 있을까요?
하스켈은 함수형 프로그래밍 언어로서, 게으른 리스트를 다룰 수 있는 강력한 기능을 가지고 있습니다. 게으른 리스트는 필요할 때만 계산되고, 필요하지 않은 부분은 계산되지 않는 특징을 갖습니다. 이러한 특징을 활용하여, 동일한 게으른 리스트에 여러 폴드 연산을 실행할 때, 중간 계산 결과를 메모리에 유지하지 않고도 가능합니다.
하스켈에서 폴드 연산을 수행하는 함수는 `foldl`과 `foldr`입니다. `foldl`은 왼쪽에서 오른쪽으로 폴드를 진행하며, `foldr`은 오른쪽에서 왼쪽으로 폴드를 진행합니다. 각각의 폴드 연산은 스트림의 원소를 한 번씩 사용하여 결과를 생성합니다. 이때, 다음 원소를 사용하기 전까지는 메모리에 원소를 유지할 필요가 없습니다.
따라서, 동일한 게으른 리스트에 여러 폴드 연산을 수행할 때, 각 폴드 연산의 결과를 변수에 저장하고 메모리에 유지할 필요 없이, 필요한 순간에 폴드 연산을 진행하여 원하는 결과를 얻을 수 있습니다. 이렇게 함으로써, 메모리 사용을 최소화하면서 효율적인 계산을 할 수 있습니다.
하스켈의 게으른 리스트는 대용량 데이터 처리 등의 상황에서 유용하게 사용될 수 있습니다. 예를 들면, 수많은 원소를 가진 리스트에 대해 여러 합산, 곱셈 연산 등을 수행해야 할 때, 게으른 리스트의 특징은 매우 유용합니다. 이는 컴퓨터 자원을 효율적으로 활용하면서 복잡한 계산을 처리할 수 있는 능력을 제공합니다.
하지만, 게으른 리스트를 사용하는 것은 항상 최적의 선택은 아닐 수 있습니다. 경우에 따라서는 메모리 사용량이 증가하거나, 계산 속도가 저하될 수 있기 때문에, 상황에 맞게 적절한 선택이 필요합니다.
이와 같이, 하스켈에서는 동일한 게으른 리스트에 여러 폴드 연산을 수행할 때, 메모리에 리스트를 유지하지 않고도 가능합니다. 이는 하스켈의 강력한 기능 중 하나로, 대용량 데이터 처리 등의 상황에서 유용하게 활용될 수 있습니다. 최적의 애플리케이션 개발을 위해서는, 상황과 요구사항에 따라 적절하게 활용하도록 주의해야 합니다.