【Common Lisp】
ハッシュテーブルの要素を順に繰り返す
（being each hash-key of）

by
  • Common Lispでハッシュテーブルを繰り返し処理する方法には、loopマクロ、maphash、with-hash-table-iteratorの3つがある。
  • loop for key being the hash-keys of tableは冗長に見えるが、集計や条件付き収集を一つの式で書けるため実用的です。
  • maphashは関数型スタイルで書けるが副作用処理向けで、hash->listを挟むとPythonのfor key, value inに近い見た目になる。

関連記事

1. ハッシュテーブルの要素を順に処理する

Common Lispでハッシュテーブルの要素を順に処理する方法はいくつかあります。

  • loop for [key] being each hash-key of [table]
  • maphash (lambda ([key] [value]) ...) [table]
  • with-hash-table-iterator ([next] [table]) ...

手続き型指向の loop マクロと関数型指向の maphash 関数があり、あとはよりプリミティブな処理のために、with-hash-table-iteratorマクロがあります1。
ちなみに、ハッシュテーブルの要素の順番は、ハッシュ値によるので要素の値とは無関係になります。
数値など順序が必要なら、できたリストを自分でソートする必要があります。

1.1. loop for … being each hash-key

ハッシュテーブルの要素ごとに処理する loopの構文は、

loop for [key] being {each | the} {hash-key | hash-keys} {in | of} [hash-table] using (hash-value [value])

loop はキーだけ、値だけ、両方の3パターンの構文があります。

;; キーだけ
(loop for key being the hash-keys of table
      collect key)

;; 値だけ
(loop for value being the hash-values of *table*
      sum value)

;; キーと値の両方
(loop for key being the hash-keys of *table*
      using (hash-value value)
      when (> value 150)
        collect key)Code language: Lisp (lisp)

loopのメリットは、かんたんな集計や条件付き収集で変数宣言がセットでできることです2。

being the hash-keys of は、loop がリスト、ベクタ、ハッシュテーブルなど多様なデータ構造を同じ構文で扱うための区別ですが、さすがに 冗長に見えます3。

Rubyの table.each do |key, value| ... end や
Pythonの for key, value in table.items(): などのように、
もっと簡潔な書き方もあったと思います。
設計当時は、CLISPという（COBOLのも通じるような）読みやすさを重視していました。

1.2. maphash とラムダ

maphash は、キーと値を受け取るラムダ式を作って、ハッシュテーブルの各要素に適用し、NILを返します4。

(maphash (lambda (key value)
           (format t "~A => ~A~%" key value))
         table)Code language: Lisp (lisp)

maphashの引数の順番は、(maphash function table) で、map系の関数は第1引数に関数を取ります5。

関数と適用対象と考えると自然ではあるのですが、処理ブロックが長くなると、maphashとtableの距離が遠くなってしまいます。

2. ハッシュテーブルの反復を書きやすくする工夫

2.1. hash->list を挟む方法

ハッシュテーブルをリストに変換する関数を用意すると、loop for (key value) in ... の形で書くことができます。

(loop for (key value) in (hash->list *table*)
      do (format t "~A => ~A~%" key value))Code language: Lisp (lisp)

for (key value) in ... の部分は分配束縛です。
だいぶ、Pythonの for key, value in ... に近い見た目になりました。

hash->list関数は、loopで実装できます。

(defun hash->list (table)
  (loop for key being the hash-keys of table
        using (hash-value value)
        collect (list key value)))Code language: Lisp (lisp)

ただし、hash->list はリスト生成のコストがあります。
ハッシュテーブル全体を一度リストに変換するため中間データが作られるため、大きなテーブルではメモリの無駄になります6。

2.2. dohashマクロを作る

何度も同じパターンを書くなら、マクロで自分好みの構文を定義できます。

(dohash (key value *table*)
  (format t "~A => ~A~%" key value))Code language: Lisp (lisp)

処理対象のテーブルが先に来て、ボディが最後に続く構造になっています。
dolist や dotimes に近い形になるように、マクロを定義すればよいわけです。

(defmacro dohash ((key value table &optional result) &body body)
  `(progn
     (maphash (lambda (,key ,value)
                ,@body)
              ,table)
     ,result))Code language: Lisp (lisp)

標準の loop が冗長に感じるなら、自分にとって読みやすい形を定義してしまえばよい。
言語自体を手元で拡張できるのがLispで、ハッシュテーブルのループ構文はその典型的な例なのかもしれません7。

3. with-hash-table-iterator という低レベルな選択肢

標準には with-hash-table-iterator もあります。

(with-hash-table-iterator (next table)
  (loop
    (multiple-value-bind (more key value) (next)
      (unless more (return))
      (format t "~A => ~A~%" key value))))Code language: Lisp (lisp)

イテレータ（反復子） next を呼ぶたびに more、key、value の3値が返ります。
継続判定more が偽になったときが反復の終端です。

with-hash-table-iteratorは、通常の用途では出番はほとんどありませんが、maphash や loop が内部でやっていることに近い形です。
途中で複雑な制御をしたいとき、仕組みを理解したいときに見ておくと参考になります8。

4. まとめ

普段のコードでは loop for key being the hash-keys of table を一番手軽です。

集計や条件付き収集も自然に書けて、コードの意図が伝わります。
あるいは、関数型で考えているときは、maphash も使えますが、副作用処理向けなのが難点かもしれません。

  1. ハッシュテーブルを走査するこれら3つの手段はすべてANSI Common Lispの標準仕様に含まれており、処理系に依存しません。 – Common Lisp HyperSpec: Macro LOOP
  2. sum や collect は loop のAccumulation節です。ハッシュテーブル走査と組み合わせて使えるのは loop の設計上の利点のひとつで、maphash や with-hash-table-iterator では同等の処理を外部変数なしには書けません。 – Common Lisp Cookbook: Hash Tables
  3. CLHSの loop のBNF定義では for-as-hash 節として being {each | the} {hash-key | hash-keys} {in | of} hash-table と規定されています。each と the、in と of はどちらも同義で、スタイルの違いのみです。 – Common Lisp HyperSpec: Macro LOOP
  4. maphash はHyperSpecで「常にNILを返す」と規定されているため、戻り値を使った処理には向きません。副作用目的に限定して使う関数です。 – Common Lisp HyperSpec: Function MAPHASH
  5. mapcar、mapc、maplist など他のmapファミリーもすべて関数を第1引数に取ります。maphash の引数順はこの慣習を踏襲したものです。 – Common Lisp HyperSpec: Function MAPC, MAPCAR…
  6. 中間リストを作らずに同様の分配束縛を行いたい場合は with-hash-table-iterator を使う方法もあります。ただし記述量が増えるため、パフォーマンスが問題にならない規模では hash->list を挟む書き方のほうが可読性で勝ります。 – Common Lisp Cookbook: Looping over Hash Tables
  7. 同様の発想でよく使われるライブラリとしてAlexandriaがあります。alexandria:hash-table-keys や alexandria:hash-table-values でキー・値のリストを直接取得でき、Quicklispで (ql:quickload "alexandria") と入力するだけで使えます。 – Alexandria Manual: Hash Tables
  8. CLHSには with-hash-table-iterator を使った maphash の参照実装が掲載されています。maphash がこのマクロを薄くラップしたものとして実装できることがわかります。ただし、イテレータをそのダイナミックエクステント外で使った場合の動作は未定義とされています。 – Common Lisp HyperSpec: Macro WITH-HASH-TABLE-ITERATOR