How do I return both a processed list and a modified object?

I'm designing a cipher called Daphne, which takes a byte of plaintext and returns an encrypted byte and a modified Daphne. When applied to a list, it should return the list of encrypted bytes and the Daphne after it has processed all the bytes. I'm not sure how to do this without taking O(n) memory. Here's the code:

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)

listEncrypt has a copy of the list in RAM as a sequence, which takes up O(n) RAM, which shouldn't be necessary.

The full code is at https://github.com/phma/daphne . It's not ready for production yet; I haven't cryptanalyzed it, let alone anyone else. I may run gigabytes of data through it and compute statistics.

Solution

I haven't really understood why you introduced sequences at all, so I may have misunderstood the problem. But it seems like recursing on the list would work fine. Something like (untested)

listEncrypt daph [] = (daph, [])
listEncrypt daph (b:bs) = (finalDaph, e:es)
  where
    (nextDaph, e) = byteEncrypt daph b
    (finalDaph, es) = listEncrypt nextDaph bs

And actually this pattern is a mapAccumL. I think byteEncrypt already has its arguments in the right order so it would just be

listEncrypt = mapAccumL byteEncrypt

Either of these should only need constant memory, but with one caveat. If you inspect the final daphne before using the encrypted list, for example by doing print (listEncrypt something something), it will have to go through the whole list to get the final daphne first while keeping the whole encrypted list in memory to be able to use that next. Print the encrypted list first and then the final daphne and it should be fine. And if you only inspect snd (listEncrypt something something) it should work even on infinite lists.