Fold on Binary

這好像是一件普通的事了,函數式程式語言的fold應該是大家都很熟悉的格式。在Erlang,如果要處理一列資料,用lists:foldl/3即可。而有一天,我們可能會想要有一個binary資料的fold。

這應該蠻簡單的。看起來,list和binary在Erlang是二個很像的資料格式。不過,將二個binary組合成一個,與將一個binary分解為二個,很顯然要用到二種不同的操作。那binary的fold有什麼不同呢?

我會寫成這樣:

fold(Scissor, Fun, State, Bin).

基本上,Fun就是二個參數,處理了資料之後,就會做合併的動作。但是,如果只平白給一個binary Bin,是不足以拆解段落的。binary是用長度來幫忙斷開,而許多現有案例,binary的長度都會放在它自己的開頭固定位置。所以,需要有一個函數叫做Scissor,它的函數型態如下:

-spec scissor(Bin :: binary()) ->
                  {Bin1 :: binary(), Bin2 :: binary}.

而要怎麼斷開binary,scissor/1自己知道,而你要自己寫scissor/1。

而加上Scissor的fold/4,其實是一個比lists:foldl/3更高抽象一層的fold。其實,lists:fold/3的Scissor是

scissor([]) -> {[], []};
scissor([H|T]) -> {H, T}.

而我想,有個fold/5是比fold/4更通用的fold。實作如下:

fold(_Scissor, _Procedure, _Accumulator, State, Data)
  when Data == <<>>; Data == [] ->;
    State;
fold(Scissor, Procedure, Accumulator, State, Data) ->
    {Data1, Data2} = Scissor(Data),
    Result = erlang:apply(Procedure, [Data1, State]),
    State1 = erlang:apply(Accumulator, [Result, State]),
    fold(Scissor, Procedure, Accumulator, State1, Data2).

Scissor斷開資料,Accumulator合併資料,Procedure則做好主要的計算工作即可。

那假如我有一段binary,每一筆記錄是開頭第三個byte offset開始用二個bytes表達這一筆記錄的長度,而我想把binary分段,變成list,就寫成這樣

S = fun(Bin) when is_binary(Bin), Bin /= <<>> ->
         Len =
           binary:decode_unsigned(binary:part(Bin, 3, 2), big),
         <<Bin1:Len/binary, Bin2/binary>> = Bin,
         {Bin1, Bin2};
       (<<>>) ->
         {<<>>, <<>>}
    end,
P = fun(Bin, _Acc) -> Bin end,
A = fun(Result, Acc) -> [Result|Acc] end,
B = [],
fold(S, P, A, B, Bin).

而在寫的時候,要稍微認清楚fold/5每個參數的型態。

然後,在上面這個程式,如果想要同時求binary有多少筆記錄,可以把A,B改成下面二行,讓一個P的計算結果發散變成二個答案,一個是筆數,一個是[binary()]。這樣的優化方式,稱為banana-split。

A = fun(Result, {N, List}) -> {N+1, [Result|Acc]} end,
B = {0, []},
廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Erlang, Programming。將永久鏈結加入書籤。