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

• みんなのデータ構造 | 技術書出版と販売のラムダノート

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

やっぱり『みんなのデータ構造』、Rustとexpl3でやりなおすかな

— keiichiro shikano λ♪ (@golden_lucky) 2018年7月29日

expl3に標準で用意されているデータ構造って何があるんだっけ？#TeX #expl3

— ZR-TeXnobabbler🤔 (@zr_tex8r) 2018年7月29日

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

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

• TeX言語者のためのexpl3入門 | ラング・ラグー

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

$ texdoc source3

シークエンス（seq型）

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

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

基本操作

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

\seq_new:N <sequence>

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

\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>はかなり自由に指定できますが、ブレース{}やパラメタ文字#を含めることはできません³。また、チョット細かい注意事項として、各要素の先頭・末尾のスペース~および一番外側のブレース{}は（もし存在すれば）除去されます。

【入力】

% シークエンスを宣言（空シークエンスに初期化）
\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という特別な値が入ります⁴。

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型の変数（あるいはその組み合わせ）などを与えることもできます。

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

複製と連結

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

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です⁶。

% すべての要素にインライン関数“( \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パッケージによって、シークエンスをソートする関数も提供されています⁷。

\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つ以上含まないもののことです⁸。

シークエンス中に重複する要素を含まないようにすると聞くと、先に紹介した\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系の関数を使用すると高速です⁹。

% 集合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）が考えられます。そのナイーブなデモ実装を以下に示します¹⁰。

% 必要な変種関数を用意
\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)