2026-10-21
Reassemble.hs
import Data.List (mapAccumL)
parse :: [Int] -> ([[Int]], [Int])
parse (n : rest)
| length body == n = let (ms, left) = parse more in (body : ms, left)
where
(body, more) = splitAt n rest
parse buf = ([], buf)
step :: [Int] -> [Int] -> ([Int], [[Int]])
step chunk buf = let (ms, left) = parse (buf ++ chunk) in (left, ms)
main :: IO ()
main = print (concat (snd (mapAccumL step [] [[2, 7], [8, 1], [5, 0]])))
TCP で細切れに届くバイト列から、メッセージの本体を順に取り出すつもりのプログラムです。各メッセージは先頭の1バイトが本体の長さを表し、そのあとにその長さの本体が続きます。parse は区切れたメッセージと、途中で切れていて次の塊を待つ残りを返し、step はその残りを次の塊に持ち越します。3つの塊 [2, 7]、[8, 1]、[5, 0] を与えると、いまは [[0,8,1,2,7]] と出力されます。本来の出力は [[7,8],[5],[]] です。
Answer
Wrong
step :: [Int] -> [Int] -> ([Int], [[Int]])
step chunk buf = let (ms, left) = parse (buf ++ chunk) in (left, ms)
parse に誤りはなく、つないだバイト列が正しければ正しく区切ります。buf ++ chunk も、名前だけ見れば「持ち越した残りのあとに新しい塊」で正しい順です。ところが mapAccumL は、渡された関数を step 持ち越し 新しい要素 の順で呼びます。step の仮引数は chunk、buf の順なので、chunk に持ち越しが、buf に新しい塊が入り、buf ++ chunk は実際には「新しい塊のあとに持ち越し」をつなぎます。どちらも [Int] なので、型検査はこの取り違えを見逃します。
1つ目の塊では持ち越しが空なので、取り違えても結果は同じです。[2, 7] は長さ2に対して本体が1個しかなく、全体が持ち越されます。2つ目でつながるのは [8, 1] ++ [2, 7] で、先頭の8が長さと読まれ、足りないので4バイトとも持ち越されます。3つ目は [5, 0] ++ [8, 1, 2, 7] で、先頭の5を長さと読むと、うしろにちょうど5バイトあるので、[0,8,1,2,7] がメッセージとして出てしまいます。正しいメッセージを取りこぼすだけでなく、長さとして読む位置がずれたせいで、でたらめな本体が正規のメッセージとして通ります。
Right
step :: [Int] -> [Int] -> ([Int], [[Int]])
step buf chunk = let (ms, left) = parse (buf ++ chunk) in (left, ms)
仮引数を mapAccumL が渡す順に合わせ、1つ目を持ち越しの buf、2つ目を新しい塊の chunk にします。2つ目の塊では [2, 7] ++ [8, 1] から [7,8] が区切れて [1] が残り、3つ目では [1] ++ [5, 0] から [5] と、長さ0の [] が区切れます1。
- 本体を
parse (chunk ++ buf)に変えても出力は直りますが、名前と中身が食い違ったまま残ります。持ち越しと新しい塊をnewtypeで別の型にしておけば、同じ取り違えは型エラーとして見つかります。