如何在不占用O(n)内存的同时返回处理后的列表与修改后的Daphne对象？

我正在设计一款名为Daphne的密码算法，它接收一个明文字节，返回加密字节和修改后的Daphne实例。处理字节列表时，需要返回加密后的字节列表，以及处理完所有字节后的Daphne实例。目前实现的listEncrypt会在内存中保存一份序列形式的列表副本，占用O(n)内存，这其实没有必要。我打算用GB级数据测试并计算统计信息，因此需要优化内存占用。

相关代码如下：

byteEncrypt :: Daphne -> Word8 -> (Daphne,Word8)
byteEncrypt (Daphne key sreg acc) plain = ((Daphne key newsreg newacc),crypt) where
  left = computeLeft key sreg acc
  right = computeRight key sreg acc
  crypt = step plain left right
  newacc = acc+plain
  newsreg = Seq.drop 1 (sreg |&> crypt)

byteDecrypt :: Daphne -> Word8 -> (Daphne,Word8)
byteDecrypt (Daphne key sreg acc) crypt = ((Daphne key newsreg newacc),plain) where
  left = computeLeft key sreg acc
  right = computeRight key sreg acc
  plain = invStep crypt left right
  newacc = acc+plain
  newsreg = Seq.drop 1 (sreg |&> crypt)

seqEncrypt :: Seq.Seq Word8 -> (Daphne,Seq.Seq Word8) -> (Daphne,Seq.Seq Word8)
seqEncrypt Seq.Empty a = a
seqEncrypt (bs:|&>b) (daph,acc) = (daph2,acc2) where
  (daph1,acc1) = seqEncrypt bs (daph,acc)
  (daph2,c) = byteEncrypt daph1 b
  acc2 = acc1 |&> c

listEncrypt :: Daphne -> [Word8] -> (Daphne,[Word8])
listEncrypt daph bs = (daph1,toList seq1) where
  (daph1,seq1) = seqEncrypt (Seq.fromList bs) (daph,Seq.Empty)

seqDecrypt :: Seq.Seq Word8 -> (Daphne,Seq.Seq Word8) -> (Daphne,Seq.Seq Word8)
seqDecrypt Seq.Empty a = a
seqDecrypt (bs:|&>b) (daph,acc) = (daph2,acc2) where
  (daph1,acc1) = seqDecrypt bs (daph,acc)
  (daph2,c) = byteDecrypt daph1 b
  acc2 = acc1 |&> c

listDecrypt :: Daphne -> [Word8] -> (Daphne,[Word8])
listDecrypt daph bs = (daph1,toList seq1) where
  (daph1,seq1) = seqDecrypt (Seq.fromList bs) (daph,Seq.Empty)

优化思路与实现 #

利用Haskell的惰性求值特性，我们可以边处理字节边生成输出列表，无需预先存储所有结果，把内存占用控制在O(1)（仅保留Daphne实例的固定大小状态，以及待处理的元素）。

惰性列表递归实现

这种写法完全利用Haskell列表的惰性，逐个生成加密/解密后的字节，不会一次性加载全部数据到内存：

listEncrypt :: Daphne -> [Word8] -> (Daphne, [Word8])
listEncrypt = go
  where
    go daph [] = (daph, [])
    go daph (b:bs) =
      let (daph', c) = byteEncrypt daph b
          (finalDaph, cs) = go daph' bs
      in (finalDaph, c:cs)

listDecrypt :: Daphne -> [Word8] -> (Daphne, [Word8])
listDecrypt = go
  where
    go daph [] = (daph, [])
    go daph (b:bs) =
      let (daph', p) = byteDecrypt daph b
          (finalDaph, ps) = go daph' bs
      in (finalDaph, p:ps)

基于foldr的高效实现

如果想更贴合Haskell的函数式风格，用foldr可以避免手动递归，同样保持惰性特性：

listEncrypt :: Daphne -> [Word8] -> (Daphne, [Word8])
listEncrypt initialDaph bs =
  foldr step (\d -> (d, [])) bs initialDaph
  where
    step b next daph =
      let (daph', c) = byteEncrypt daph b
          (finalDaph, cs) = next daph'
      in (finalDaph, c:cs)

listDecrypt :: Daphne -> [Word8] -> (Daphne, [Word8])
listDecrypt initialDaph bs =
  foldr step (\d -> (d, [])) bs initialDaph
  where
    step b next daph =
      let (daph', p) = byteDecrypt daph b
          (finalDaph, ps) = next daph'
      in (finalDaph, p:ps)

关键注意事项 #

1. 严格状态更新：确保Daphne类型的字段是严格求值的（比如在定义时用!标记字段），避免因惰性导致的thunk积累，额外占用内存。
2. 改用ByteString处理大文件：如果处理GB级数据，建议使用ByteString替代普通列表，它是更高效的字节存储结构，内存占用更低、处理速度更快。示例实现：

import Data.ByteString (ByteString)
import qualified Data.ByteString as BS

bsEncrypt :: Daphne -> ByteString -> (Daphne, ByteString)
bsEncrypt initialDaph bs =
  BS.foldr step (\d -> (d, BS.empty)) bs initialDaph
  where
    step b next daph =
      let (daph', c) = byteEncrypt daph b
          (finalDaph, cs) = next daph'
      in (finalDaph, BS.cons c cs)

内容的提问来源于stack exchange，提问作者Pierre Abbat