2019年2月2日土曜日

ISBNチェッカー（循環リストの応用例）

循環リストの応用例

最近、ISBNの入力ミスを発見するためのスクリプトを書いた。
循環リストを使った美しいコードだと思う。

だけど、「循環リスト（Circular list）なんて観念で、
（理論の）完全性のために存在しているだけ」と言われることがある。
また、Googleで「循環リスト」を検索すると
関連検索として「循環リスト 応用例」を提案してくる。

でも、循環リストを使わないと実現しにくいアルゴリズムもあるし、
循環リストはSchemeの楽しさを高めている思っている。
そして私はこよなくschemeを愛している。
だから、ここに実用的な「循環リストの応用例」として
ISBNチェッカーを公開する。

ISBNチェッカー

ISBNは書籍を一意に示すための番号である。
ISBN-13の最後の1桁はチェックデジットであり、以下のように計算される。
----- -----
現行規格のISBN (ISBN-13) のチェックディジットは、JANコードと同じく、「モジュラス10 ウェイト3・1（モジュラス10 ウェイト3）」という計算法にて算出される。（チェックディジットを除いた一番左側の桁から順に1、3、1、3…を掛けてそれらの和を取る。和を10で割って出た余りを10から引く。ただし、10で割って出た余りの下1桁が0の場合はチェック数字を0とする。）
----- -----
「ISBN」（2018年12月21日 (金) 08:59UTCの版）『ウィキペディア日本語版』より引用[注1]。

これを実装すると以下のようになる。ただし、入力は文字列として受け取る。
(use srfi-1)
(define (check-isbn13 num)
  (define weight (circular-list 1 3))
  (zero? (remainder (fold + 0 (map (lambda (x y) (* x y))
                   weight
                   (map digit->integer (string->list num))))
            10)))
「一番左側の桁から順に1、3、1、3…を掛け」るところに循環リストを使っている （(circular-list 1 3)は'(1 3 1 3 ...)となる循環リストを返す。）。
左から1桁ずつループして拾っているのだけど、
掛ける数が1と3で交互なので、
(1 3 1 3 ...)となっている循環リストに対して、
carで先頭を拾って使い、cdrして残りを次のiterationに渡している。
場合分けとかフラグとかを使っていないところが美しいでしょう？

うさぎとかめのアルゴリズム

ところで、あるリストを与えられた時、それが循環リストになっているかをチェックする コードが以下にある。
大変美しく、ぜひご覧いただきたいので、ここで勝手に紹介する。

以上
投稿者 時刻: