在不断努力有效地摆弄位的过程中（例如，请参阅此所以问题 https://stackoverflow.com/questions/43601927/efficient-bit-fiddling-in-a-lfsr-implementation）最新的挑战是高效的流传输和比特消耗。
作为第一个简单任务，我选择在由以下命令生成的比特流中找到最长的相同比特序列/dev/urandom。一个典型的咒语是head -c 1000000 </dev/urandom | my-exe。实际目标是传输比特并解码埃利亚斯伽玛码 https://en.wikipedia.org/wiki/Elias_gamma_coding，例如，即不是字节块或其倍数的代码。
对于这种可变长度的代码，最好有take, takeWhile, group等列表操作语言。自从一个BitStream.take实际上会消耗一些 monad 可能会发挥作用的比特流的一部分。
明显的起点是来自的惰性字节串Data.ByteString.Lazy http://hackage.haskell.org/package/bytestring-0.10.8.2/docs/Data-ByteString-Lazy.html.
A. 计算字节数
正如预期的那样，这个非常简单的 Haskell 程序的性能与 C 程序相当。
import qualified Data.ByteString.Lazy as BSL
main :: IO ()
main = do
bs <- BSL.getContents
print $ BSL.length bs
B. 添加字节
一旦我开始使用unpack事情应该变得更糟。
main = do
bs <- BSL.getContents
print $ sum $ BSL.unpack bs
令人惊讶的是，Haskell 和 C 表现出几乎相同的性能。
C. 最长的相同位序列
作为第一个重要任务，可以像这样找到最长的相同位序列：
module Main where
import Data.Bits (shiftR, (.&.))
import qualified Data.ByteString.Lazy as BSL
import Data.List (group)
import Data.Word8 (Word8)
splitByte :: Word8 -> [Bool]
splitByte w = Prelude.map (\i-> (w `shiftR` i) .&. 1 == 1) [0..7]
bitStream :: BSL.ByteString -> [Bool]
bitStream bs = concat $ map splitByte (BSL.unpack bs)
main :: IO ()
main = do
bs <- BSL.getContents
print $ maximum $ length <$> (group $ bitStream bs)
惰性字节串转换为列表[Word8]然后，利用轮班，每个Word被分成几位，产生一个列表[Bool]。然后将这个列表列表展平为concat。获得了（惰性）列表Bool, use group将列表拆分为相同位的序列，然后映射length超过它。最后maximum给出了所需的结果。很简单，但不是很快：
# C
real 0m0.606s
# Haskell
real 0m6.062s
这种幼稚的实现正好慢了一个数量级。
分析显示分配了相当多的内存（解析 1MB 输入大约需要 3GB）。不过，没有观察到大规模的空间泄漏。
从这里我开始四处探索：
- 有一个bitstream package https://hackage.haskell.org/package/bitstream-0.2.0.4/docs/Data-Bitstream.html承诺“具有半自动流融合的快速、打包、严格的比特流（即布尔列表）。”。不幸的是，它与当前的情况不同步。
vector包，参见here https://github.com/depressed-pho/bitstream/issues/6了解详情。
- 接下来我调查一下streaming https://hackage.haskell.org/package/streaming。我不太明白为什么我应该需要“有效”的流媒体来发挥一些单子的作用——至少在我开始与所提出的任务相反的任务之前，即编码并将比特流写入文件。
- 就这样怎么样
fold- 超过ByteString？我必须引入状态来跟踪消耗的位。这不太好take, takeWhile, group等所需的语言。
现在我不太确定该去哪里。
Update:
我想出了如何做到这一点streaming https://hackage.haskell.org/package/streaming-0.2.1.0 and streaming-bytestring https://hackage.haskell.org/package/streaming-bytestring-0.1.6/docs/Data-ByteString-Streaming.html。我可能做得不对，因为结果是灾难性的糟糕。
import Data.Bits (shiftR, (.&.))
import qualified Data.ByteString.Streaming as BSS
import Data.Word8 (Word8)
import qualified Streaming as S
import Streaming.Prelude (Of, Stream)
import qualified Streaming.Prelude as S
splitByte :: Word8 -> [Bool]
splitByte w = (\i-> (w `shiftR` i) .&. 1 == 1) <$> [0..7]
bitStream :: Monad m => Stream (Of Word8) m () -> Stream (Of Bool) m ()
bitStream s = S.concat $ S.map splitByte s
main :: IO ()
main = do
let bs = BSS.unpack BSS.getContents :: Stream (Of Word8) IO ()
gs = S.group $ bitStream bs :: Stream (Stream (Of Bool) IO) IO ()
maxLen <- S.maximum $ S.mapped S.length gs
print $ S.fst' maxLen
这将考验您对来自标准输入的超过几千字节输入的耐心。分析器表示它花费了大量的时间（输入大小的二次方）Streaming.Internal.>>=.loop and Data.Functor.Of.fmap。我不太确定第一个是什么，但是fmap表明（？）这些杂耍Of a b对我们没有任何好处，而且因为我们处于 IO monad 中，所以无法对其进行优化。
我还有字节加法器的流式传输等效项here: SumBytesStream.hs https://github.com/mcmayer/haskell-efficient-bitstreams/blob/master/SumBytesStream.hs，比简单的lazy稍微慢一点ByteString实施，但仍然不错。自从streaming-bytestring is 宣布 https://hackage.haskell.org/package/streaming-bytestring to be "字节串 io 正确完成“我的预期更好。那么我可能做得不对。
无论如何，所有这些位计算都不应该发生在 IO monad 中。但BSS.getContents迫使我进入 IO monad 因为getContents :: MonadIO m => ByteString m ()并且没有出路。
Update 2
按照@dfeuer的建议，我使用了streaming https://github.com/haskell-streaming/streaming包位于 master@HEAD。这是结果。
longest-seq-c 0m0.747s (C)
longest-seq 0m8.190s (Haskell ByteString)
longest-seq-stream 0m13.946s (Haskell streaming-bytestring)
O(n^2) 问题Streaming.concat已经解决了，但是我们仍然没有接近 C 基准。
Update 3
Cirdec 的解决方案产生与 C 相当的性能。所使用的构造称为“Church 编码列表”，请参阅此所以答案 https://stackoverflow.com/questions/15589556/why-are-difference-lists-not-an-instance-of-foldable/15593349#15593349或 Haskell Wiki 上N 级类型 https://wiki.haskell.org/Rank-N_types.
源文件：
所有源文件都可以在github https://github.com/mcmayer/haskell-efficient-bitstreams. The Makefile具有运行实验和分析的所有各种目标。默认make只会构建一切（创建一个bin/首先是目录！）然后make time将进行计时longest-seq可执行文件。 C 可执行文件得到一个-c附加以区分它们。
