expl3 の標準データ構造 (1) seq

2018-08-10   #expl3 

某ラム社の新刊が人気沸騰中のようです.

今後,あらゆるプログラミング言語で様々なデータ構造を実装することが流行っていく機運があり,expl3 についてもその例に漏れていないようです.なんと某ランダムノート社社長も参戦を仄めかしているほどです.

というわけで,これから expl3 で各種のデータ構造を実装する人のために,expl3 が標準でサポートしているデータ構造について,それぞれの特徴と基本的な使い方を,何回かに分けて解説していこうと思います.

なお expl3 そのものの基礎事項については,以下の記事を参照してください.

また expl3 のフルリファレンスは source3.pdf です.例によって Texdoc で簡単に表示できます:

$ texdoc source3

シークエンス(seq 型)

私見ですが,expl3 において最も基本的なデータ構造はシークエンスです.expl3 のシークエンスは,巷でいうところの1次元の順序付きリストに相当し,任意の <balanced text>1 を要素とすることができます.

シークエンスの最大の特徴は,あるシークエンスがもつすべての要素に同一の関数を適用するいわゆる「マップ操作」が高速に行えることです.また,シークエンスは「スタック」としても利用するにも便利で,l3seq パッケージによってそのためのユーテリティが数多く提供されています.

基本操作

まず,シークエンスを使用するためには

\seq_new:N <sequence>

のように seq 型の変数を宣言してやる必要があります.\<type>_new:N 型の変数宣言はすべてグローバルなので,\seq_new:N の効果ももちろんグローバルです.また,<sequence> が既に存在している場合はエラーになるので注意しましょう2

\seq_new:N により宣言した <sequence> は自動的に空のシークエンスに初期化されます.シークエンスの内容は \seq_show:N\seq_log:N でそれぞれコンソール,ログファイルに出力することもできます.

【入力】

% シークエンスを宣言(空シークエンスに初期化)
\seq_new:N \l_test_seq  % \l_test_seq = []

% コンソール出力
\seq_show:N \l_test_seq

【コンソール出力】

The sequence \l_test_seq is empty
> .

シークエンスに値を追加するには,基本的には \seq_put_left:Nn\seq_put_right:Nn を用います.関数名の通りですが,それぞれシークエンスの先頭と末尾に値を1つ追加します.

【入力】

% 要素を先頭に追加
\seq_put_left:Nn \l_test_seq { ab }    % \l_test_seq = [ab]
\seq_put_left:Nn \l_test_seq { c }     % \l_test_seq = [c, ab]

% 要素を末尾に追加
\seq_put_right:Nn \l_test_seq { def }  % \l_test_seq = [c, ab, def]

% コンソール出力
\seq_show:N \l_test_seq

【コンソール出力】

The sequence \l_test_seq contains the items (without outer braces):
>  {c}
>  {ab}
>  {def}.

要素を一括設定する

シークエンスに1つずつ値を設定するのが大変な場合は,まとめて設定してしまった方が楽でしょう.そんなときに便利なのが \seq_set_split:Nnn 関数です.

\seq_set_split:Nnn <sequence> {<delimiter>} {<token list>}

この関数は <token list> を指定した <delimiter> で区切って,それぞれをシークエンスの要素にします.<delimiter> はかなり自由に指定できますが,ブレース {} やパラメタ文字 # を含めることはできません3.また,チョット細かい注意事項として,各要素の先頭・末尾のスペース ~ および一番外側のブレース {} は(もし存在すれば)除去されます.

【入力】

% シークエンスを宣言(空シークエンスに初期化)
\seq_new:N \l_essential_seq

% 値をまとめて設定
\seq_set_split:Nnn \l_essential_seq { | } {
  snowman | {duck} | ~sushi~
}  % \l_essential_seq = [snowman, duck, sushi]

% コンソール出力
\seq_show:N \l_essential_seq

【コンソール出力】

The sequence \l_essential_seq contains the items (without outer braces):
>  {snowman}
>  {duck}
>  {sushi}.

要素を取り出す

シークエンスから要素を取り出す方法は色々ありますが,基本となるのは特定の位置の要素を tl 型の変数に取り出すものです.特に,先頭または末尾にある要素を取り出すのには専用の関数が存在します.

% シークエンスを宣言&値を設定
\seq_new:N \l_number_seq
\seq_set_split:Nnn \l_number_seq { | } {
  0 | 1 | 2 | 3
}  % \l_number_seq = [0, 1, 2, 3]

% 先頭の要素を取り出し,シークエンスからは削除
\seq_pop_left:NN \l_number_seq \l_tmpa_tl   % \l_tmpa_tl = 0, \l_number_seq = [1, 2, 3]

% 先頭の要素を取り出す
\seq_get_left:NN \l_number_seq \l_tmpa_tl   % \l_tmpa_tl = 1, \l_number_seq = [1, 2, 3]

% 末尾の要素を取り出し,シークエンスからは削除
\seq_pop_right:NN \l_number_seq \l_tmpa_tl  % \l_tmpa_tl = 3, \l_number_seq = [1, 2]

% 末尾の要素を取り出す
\seq_get_right:NN \l_number_seq \l_tmpa_tl  % \l_tmpa_tl = 2, \l_number_seq = [1, 2]

ここで \seq_pop_left:NN および \seq_pop_right:NN によるシークエンスからの要素の削除はローカルに行われます.この操作をグローバルに適用するにはそれぞれ \seq_gpop_left:NN\seq_gpop_right:NN が使えます.これらの関数を用いても,tl 型変数への要素の代入はローカルに行われるので注意が必要です.また,上述の関数で要素を取り出そうとしたシークエンスが空の場合,取り出し先の tl 型変数には \q_no_value という特別な値が入ります4

TeX 言語を書いたことのある読者であればわかると思いますが,TeX 言語で「関数から関数へ値を受け渡す」方法は「特定の制御綴を介する」以外にも(一般に,実装の難易度は上がりますが)「展開結果が返り値となるようにする」という手があります.単純な例では

\cs_new:N \my_test:n #1 { (#1) }

という関数は引数を1つとって,その内容をパーレン () で囲ったものを「展開結果として」返します.当たり前のことですが,「展開される場所」が何らかの関数の引数内でなければ,展開結果はそのまま PDF に出力されることになります.このような値の返し方を,expl3 の用語では「入力ストリームに返す」と表現します.

シークエンスから値を取り出すもう1つの方法は,シークエンス中の指定した位置の要素を入力ストリームに取り出す \seq_item:Nn 関数です.これを用いると,先頭・末尾以外の任意の位置から値を取り出すことができます.

\seq_item:Nn <sequence> {<integer expression>}

大方の予想通り,上記の書式によって <sequence><integer expression> 番目の要素が入力ストリームに取り出されます.第2引数は <integer expression> なので,直に書かれた整数だけでなく 1+2 のように簡単な演算を要求するものや int 型の変数(あるいはその組み合わせ)などを与えることもできます.

ただし,シークエンスの末尾や任意位置から要素を取り出すのは,先頭の要素を取り出すほど効率的ではないので,あまり頻繁に使用すると実行速度の低下に繋がります5

複製と連結

早くも理解の難しい概念の導入はほとんど済んでしまったので(おめでとうございます🎉),ここからは具体例ベースでサクサク進んでいきます.

l3seq パッケージは,もちろんシークエンスの複製(コピー)や連結を行うための関数も提供しています.

% シークエンスを3つ宣言
\seq_new:N \l_important_one_seq
\seq_new:N \l_important_two_seq
\seq_new:N \l_important_final_seq

% 値をまとめて設定
\seq_set_split:Nnn \l_important_one_seq { | } {
  TeX | is | evil
}  % \l_important_one_seq = [TeX, is, evil]

% シークエンスを複製
\seq_set_eq:NN \l_important_two_seq \l_important_one_seq 
  % \l_important_two_seq = [TeX, is, evil]

% シークエンスを結合
\seq_concat:NNN \l_important_final_seq
  \l_important_one_seq \l_important_two_seq
  % \l_important_final_seq = [TeX, is, evil, TeX, is, evil]

「TeX はアレ,TeX はアレ」大事なことなので2回言いました.

シークエンスの変更操作

ここに並ぶのは,シークエンスを変更する便利な関数たちです.

% シークエンスを宣言&値を設定
\seq_new:N \l_duck_seq
\seq_set_split:Nnn \l_duck_seq { | } {
  duck | duck | duck | snowman | duck | duck
}  % \l_important_one_seq = [duck, duck, duck, snowman, duck, duck]

% 反転
\seq_reverse:N \l_duck_seq
  % \l_important_one_seq = [duck, duck, snowman, duck, duck, duck]

% 重複を削除
\seq_remove_duplicates:N \l_duck_seq
  % \l_important_one_seq = [duck, snowman]

% 特定要素を全削除
\seq_remove_all:Nn \l_duck_seq { duck }
  % \l_duck_seq = [snowman]

生き残ったのは “醜いアヒルの子” でした(えっ)

条件分岐

シークエンスの状態によって条件分岐する関数もあります.

% シークエンスを宣言&値を設定
\seq_new:Nn \l_engine_seq
\seq_set_split:Nnn \l_engine_seq { | } {
  TeX | XeTeX | LuaTeX
}  % \l_engine_seq = [TeX, XeTeX, LuaTeX]

% 空シークエンスか否か
\seq_if_empty:NTF \l_engine_seq { true } { false } %=>false

% 指定した要素 (XeTeX) を含むか
\seq_if_in:NnTF \l_engine_seq { XeTeX } { true } { false } %=>true

シークエンスを直接使用する

シークエンスの全要素を入力ストリームに吐き出すには \seq_use:* 系の関数を用います.

\seq_use:Nnnn <sequence> {<separator between two>}
  {<separator between more than two>} {<separator between final two>}

\seq_use:Nnnn は最も高機能なもので,すべて字面通りですが

  • 第2引数 <separator between two>: 要素が2つのときに使用されるセパレータ
  • 第3引数 <separator between more than two>: 要素が3つ以上のときに使用されるセパレータ
  • 第4引数 <separator between final two>: 要素が3つ以上のとき,最後の1回のみ使用されるセパレータ

と極めて細かにセパレータを設定することができます.

\seq_set_split:Nnn \l_tmpa_seq { | } { a | b | c | {de} | f }
\seq_use:Nnnn \l_tmpa_seq { ~and~ } { ,~ } { ,~and~ } %=>a, b, c, de, and f

ここまで細かにセパレータを指定する必要がない場合は,\seq_use:Nn の方がお手軽です.

\seq_use:Nn <sequence> {<separator>}

マップ操作

マップ操作というのは,簡単に言えばシークエンスのすべての要素に同一の操作を適用することです.

まず,特定の関数を指定して,その関数をシークエンスのすべての要素に適用するためには \seq_map_function:NN を用います.

\seq_map_function:NN <sequence> <function>

これにより指定した <function><sequence> の先頭から末尾に向かってすべての要素に適用されます.

% シークエンスを初期化&値を設定
\seq_clear_new:N \l_number_seq
\seq_set_split:Nnn \l_number_seq { | } {
  1 | 2 | 3
}  % \l_number_seq = [1, 2, 3]

% すべての要素に \int_to_alph:n を適用
\seq_map_function:NN \l_number_seq \int_to_alph:n %=>abc

また,特定の関数を指定するかわりにインライン関数として,その場でマップしたい処理を記述する方法もあります.expl3 におけるインライン関数とは,他の言語でいうラムダ抽象や無名関数に相当するものですが,束縛変数の名前は自由に変えられず常に #1 です6

% すべての要素にインライン関数 “( \int_eval:n { #1 * 3 } )” を適用
\seq_map_inline:Nn \l_number_seq {
  ( \int_eval:n { #1 * 3 } )
} %=>(3)(6)(9)

なお処理速度は \seq_map_inline:Nn の方が \seq_map_function:NN より数十倍速いようです.

ところで,マップ操作は \seq_map_break: 関数によって中断することも可能です.この関数には引数ありバージョンの \seq_map_break:n もあり,中断時に引数に与えたコードが実行されます.

% 要素が3以上のときにマップ操作を中断
\seq_map_inline:Nn \l_number_seq {
  \int_compare:nNnTF { #1 } < { 3 } {
    % 3未満の要素は3倍して入力ストリームへ送る
    ( \int_eval:n { #1 * 3 } )
  }{
    % 3以上の要素が来たら “[END]” を入力ストリームへ送り,マップ操作を中断(終了)
    \seq_map_break:n { [END] }
  }
} %=>(3)(6)[END]

ソート

l3sort パッケージによって,シークエンスをソートする関数も提供されています7

\seq_sort:Nn <sequence> {<comparison code>}

ここで <comparison code> には #1#2 より「前」にあるべきなら \sort_return_same:,そうでない(#1#2 を入れ替える必要がある)なら \sort_return_swapped: を入力ストリームに返すようなインライン関数を指定します.

% シークエンスを初期化&値を設定
\seq_clear_new:N \l_number_seq
\seq_set_split:Nnn \l_number_seq { | } {
  3 | 01 | -2 | 5 | +1
}  % \l_number_seq = [3 , 01 , -2 , 5 , +1]

% 数値の大小でソート
\seq_sort:Nn \l_number_seq
  {
    \int_compare:nNnTF { #1 } > { #2 }
      { \sort_return_swapped: }
      { \sort_return_same: }
  }  % \l_number_seq = [-2 , 01 , +1 , 3 , 5]

集合としてのシークエンス

ここからは,ここまでに登場した関数を用いたシークエンスのチョット応用的な使い方を紹介します.

まずは公式ドキュメントにも載っている例で,シークエンスを集合 (set) として使用することを考えます.ここで「集合」というのは,1つのシークエンスの中に “同一の要素” を2つ以上含まないもののことです8

シークエンス中に重複する要素を含まないようにすると聞くと,先に紹介した \seq_remove_duplicates:N 関数が便利そうです.しかし,この関数の動作は決して高速ではない上,集合(とみなしているシークエンス)に一時的とはいえ重複要素が存在することになってしまうので,要素追加時に既に同一要素が存在していないかチェックを行う方針を採ることにします.

% 集合に要素を追加: #1 = sequence, #2 = item
\cs_new:Npn \seq_as_set_add:Nn #1#2 {
  % 加えたい要素 #2 がシークエンス #1 に含まれていないときのみ
  % 新要素 #2 をシークエンス #1 (の末尾) に追加
  \seq_if_in:NnF #1 { #2 } { \seq_put_right:Nn #1 { #2 } }
}

% === 使用例 ===
% 集合として使用したいシークエンスを宣言
\seq_new:N \l_my_set_seq

% 集合に1, 2, 3を追加
\seq_as_set_add:Nn \l_my_set_seq { 1 }  % \l_my_set_seq = [1]
\seq_as_set_add:Nn \l_my_set_seq { 2 }  % \l_my_set_seq = [1, 2]
\seq_as_set_add:Nn \l_my_set_seq { 3 }  % \l_my_set_seq = [1, 2, 3]

% 集合にもう一度2を追加……することはできない
\seq_as_set_add:Nn \l_my_set_seq { 2 }  % \l_my_set_seq = [1, 2, 3]

また2つの集合の共通部分 (intersection) や和集合 (union) を計算したい場合には \seq_map_inline:Nn 系の関数を使用すると高速です9

% 集合 A, B の共通部分 (A∩B) を集合 C に格納:
%   #1 = 集合 C, #2 = 集合 A, #3 = 集合 B
\cs_new:Npn \seq_as_set_intersection:NNN #1#2#3 {
  % 集合 C を初期化
  \seq_clear:N #1
  % 共通部分を集合 C に代入
  \seq_map_inline:Nn #2 {
    % ここでは集合 A の各要素が ##1 に入る.
    % ##1 が集合 B にも含まれていれば,集合 C に追加
    \seq_if_in:NnT #3 { ##1 } {
      \seq_put_right:Nn #1 { ##1 }
    }
  }
}

% 集合 A, B の和集合 (A∪B) を集合 C に格納:
%   #1 = 集合 C, #2 = 集合 A, #3 = 集合 B
\cs_new:Npn \seq_as_set_union:NNN #1#2#3 {
  % 集合 C に集合 A をコピー
  \seq_set_eq:NN #1 #2
  % 集合 A に含まれていない集合 B の要素を集合 C に追加
  \seq_map_inline:Nn #3 {
    % ここでは集合 B の各要素が ##1 に入る
    \seq_if_in:NnF #1 { ##1 } {
      \seq_put_right:Nn #1 { ##1 }
    }
  }
}

% === 使用例 ===
% 集合 A, B, C を用意
\seq_new:N \l_my_seta_seq
\seq_new:N \l_my_setb_seq
\seq_new:N \l_my_setc_seq

% 集合 A に要素を追加
\seq_as_set_add:Nn \l_my_seta_seq { 1 }  % \l_my_seta_seq = [1]
\seq_as_set_add:Nn \l_my_seta_seq { 2 }  % \l_my_seta_seq = [1, 2]

% 集合 B に要素を追加
\seq_as_set_add:Nn \l_my_setb_seq { 1 }  % \l_my_setb_seq = [1]
\seq_as_set_add:Nn \l_my_setb_seq { 3 }  % \l_my_setb_seq = [1, 3]

% A∩B を C に代入
\seq_as_set_intersection:NNN \l_my_setc_seq \l_my_seta_seq \l_my_setb_seq
  % \l_my_setc_seq = [1]

% A∪B を C に代入
\seq_as_set_union:NNN \l_my_setc_seq \l_my_seta_seq \l_my_setb_seq
  % \l_my_setc_seq = [1, 2, 3]

シークエンスのシークエンス(2次元シークエンス)

2018年8月現在,残念なことに expl3 には公式には多次元のデータ構造が存在しません.つまり,expl3 コーディングで多次元のデータ構造が必要になった場合は自前で実装をする必要があります.

そのアプローチの1つに「シークエンスのシークエンス」(以下 seq_in_seq)が考えられます.そのナイーブなデモ実装を以下に示します10

% 必要な変種関数を用意
\cs_generate_variant:Nn \seq_set_split:Nnn { cnn }

% seq_in_seq 宣言用命令: #1 = seq_in_seq
\cs_new:Npn \seq_in_seq_new:N #1 {
  % シークエンス本体を初期化
  \seq_new:N #1
  % インデックス用整数も初期化
  \int_new:c { l_ \cs_to_str:N #1 _index_int }
}

% seq_in_seq にシークエンスを追加(ここでは “|” 区切り固定):
%   #1 = seq_in_seq, #2 = “|” 区切りの要素
\cs_new:Npn \seq_in_seq_add:Nn #1#2 {
  % インデックスをインクリメント
  \int_incr:c { l_ \cs_to_str:N #1 _index_int }
  % 内部シークエンスの名前を \l_tmpa_tl に保持
  \tl_set:Nx \l_tmpa_tl {
    l_inner_ \cs_to_str:N #1 _ \int_use:c { l_ \cs_to_str:N #1 _index_int }
  }
  % 内部シークエンスを宣言
  \seq_new:c { \l_tmpa_tl }
  % 内部シークエンスに要素を代入
  \seq_set_split:cnn { \l_tmpa_tl } { | } { #2 }
  % 内部シークエンスを対象の seq_in_seq に追加
  \exp_args:NNc \seq_put_right:Nn #1 { \l_tmpa_tl }
}

% seq_in_seq 中の任意要素の取り出し:
%   #1 = seq_in_seq, #2 = インデックス1, #3 = インデックス2
\cs_new:Npn \seq_in_seq_item:Nnn #1#2#3 {
  \seq_item:cn { l_inner_ \cs_to_str:N #1 _ \int_eval:n { #2 } } { #3 }
}

% === 使用例 ===
% seq_in_seq を宣言
\seq_in_seq_new:N \l_my_seq_in_seq

% seq_in_seq にシークエンスを3つ追加
\seq_in_seq_add:Nn \l_my_seq_in_seq { 1 | 2 | 3 }
\seq_in_seq_add:Nn \l_my_seq_in_seq { 4 | 5 | 6 }
\seq_in_seq_add:Nn \l_my_seq_in_seq { 7 | 8 | 9 }

% seq_in_seq から2番目のシークエンスの2番目の要素を取り出す
\seq_in_seq_item:Nnn \l_my_seq_in_seq { 2 } { 2 }  %=>5

多次元のデータ構造を expl3 上で実装する方法としては,他に tl 型変数の動的生成による「疑似配列」なども考えられますが,seq_in_seq のメリットとして

  • l3seq パッケージが提供する機能の多くをそのまま流用できる
  • 制御綴の無駄遣いが(比較的)少ない

ということが挙げられます.一方で

  • (内部シークエンス要素への)ランダムアクセスが遅い
  • 真面目に実装しようとすると,たぶん展開制御の闇に飲まれる

などのデメリットもあり,一長一短と言えそうです.

次回:プロパティリスト (prop) とカンマ区切りリスト (clist)


  1. The TeXbook 由来の概念で,{} の釣り合いの取れたトークン列. [return]
  2. <sequence> が既に存在している可能性がある場合は \seq_clear_new:N を使用すると,<sequence> が存在しない場合は宣言,存在する場合は初期化をしてくれて便利です. [return]
  3. <delimiter> を指定しない場合は TeX のトークン区切りになります. [return]
  4. こうした \q_ から始まる変数は quark という expl3 で用いられる特殊な制御綴です.quark についての詳細な説明は別の機会にとっておくことにして,本稿では割愛します. [return]
  5. もう少し正確に言えばシークエンスの先頭・末尾からの要素取り出しは定数時間 $O(1)$ ですが,$n$ 番目の要素取り出しは線形時間 $O(n)$ です(訂正:TeX 上における計算量の評価は思っていたより複雑なようなので,この注の内容は撤回します). [return]
  6. どうしても束縛変数に名前を与えたい場合は \seq_map_variable:NNn <sequence> <variable> {<code>} を用いると <variable> に要素を代入した上で <code> を実行させることができます. [return]
  7. l3sort が提供する各種データ構造に対するソートの実装はマージソートになっています.したがって,要素数 $n$ のシークエンスにかかる時間は $O(n\log n)$ です.マージソートは最悪・平均時間計算量がともに $O(n\log n)$ であり,また安定ソートでもあるので,汎用のソート関数の実装に採用するのは妥当な判断と言えるでしょう. [return]
  8. 多くのプログラミング言語で「集合」と言った場合は,「同じ要素を含まない」ということに加えて「順序が保証されない」という性質があります.しかし,expl3 のシークエンスは順序が保証されるデータ構造なので,これを集合として転用する限りは実際には順序は保存されます(ただし使用するときには順序を仮定しない方がいいでしょう). [return]
  9. 関数定義(\cs_new:Npn の第3引数)の中でインライン関数のために #1 を書きたい場合は # をエスケープして ##1 のように書く必要がある点に注意. [return]
  10. ただし,この実装は内部シークエンスの削除や並び替えには一切対応していないので,実用するためにはもう少し工夫を加える必要がありそうです. [return]