GaucheでRubyのArray#product同等の関数

gauche

結論

Gaucheではcartesian-productを使うと良い。
以下は、この関数を見落としていたことによる悪戦苦闘の記録。

背景

業務中にちょっとしたスクリプトで「複数の配列の直積」が必要になった。

例:

  • 入力: [[1, 2], [3, 4], [5]]
  • 出力: [[1, 3, 5], [1, 4, 5], [2, 3, 5], [2, 4, 5]]

2配列ぐらいなら2重ループでもいいのだけど、6配列ぐらい必要だったのでループはきつかった。

RubyのArray#product

業務中は作業速度優先で、さっさとRubyで対応した。Rubyならそのものproductというのがある。

irb(main):001:0> [1, 2].product([3, 4], [5])
=> [[1, 3, 5], [1, 4, 5], [2, 3, 5], [2, 4, 5]]

Gaucheにproductがあるのか調べる

業務後にGaucheでどう書くか調べてみた。
冒頭に書いた通り標準ライブラリに存在するのだけど、この時点では見落としていた。

まず(apropos 'product)で引っかからないので早とちりしたが、ドキュメントにちゃんと書いてあった。

Macro: apropos pattern :optional module
名前がpatternにマッチするような定義された変数のリストを表示します。 moduleにモジュールオブジェクトまたはモジュール名を与えた場合は、 そのモジュール内で定義されている変数のみが表示されます。moduleが 省略された場合は、カレントモジュールから「見える」変数が全て表示されます。

カレントモジュールから「見える」変数が全て表示されます。

cartesian-productはutil.combinationsにあるので、useしないと見えなかった。
(どこにあるか分からない段階でuse出来るわけはないので、これは仕方ないが)

gosh> (use util.combinations)
gosh> (apropos 'product)
cartesian-product              (util.combinations)
cartesian-product-for-each     (util.combinations)
cartesian-product-right        (util.combinations)
cartesian-product-right-for-each (util.combinations)

とはいえDashでproductで引っ掛ければcartesian-productが引っかかるので、これは単純に見落とした。

そんなわけでproduct関数がないと思い込み、練習ついでにGaucheで書いてみようと思った。

Rubyで仮実装

最初からGaucheで書けるほど慣れていないので、まずはRubyで書いてみた。
自己再帰で書いたりしたのだけど最終的にはinjectを使うようにした。

# 2要素の直積
def product_2dim(xs, ys)
  xs.inject([]) do |acc, x|
    acc + ys.map do |y|
      [x, y].flatten
    end
  end
end

# injectで畳み込み
def product(*lists)
  lists.inject([[]]) {|acc, ls|
    product_2dim(acc, ls)
  }
end

Gaucheで実装

上記のRuby実装をGaucheで置き換えた。

(define (product . lis)
  (define (append-last a b)
    (if (null? a)
        (list b)
        (append a (cons b '()))))

  (define (product-2dim xs ys)
    (fold (^(y acc)
            (append acc (map (cut append-last y <>) xs)))
          '() ys))

  (fold product-2dim '(()) lis))

期待通りには動いているように見える。でも…

ベンチマーク取ってみた

(let ((a (iota 100 1))
      (b (iota 100 1))
      (c (iota 100 1)))
  (time (product a b c)))

; (time (product a b c))
;  real 203.288
;  user 279.670
;  sys   16.460

遅い。非効率な実装なのは感じていたけど、ここまで遅いとは。
ちなみにもちろんcartesian-product使えばちゃんと早い。

(use util.combinations)
(let ((a (iota 100 1))
      (b (iota 100 1))
      (c (iota 100 1)))
  (time (cartesian-product (list a b c))))

;(time (cartesian-product (list a b c)))
; real   0.347
; user   0.330
; sys    0.020

おわりに

自分で書いたproduct実装は遅いのを抜きにしても可読性が悪い。これ絶対数日後に読んでも何がしたいか解読に時間がかかるパターン。
色々書いて読んで覚えていくしかない。

cartesian-product自体Gaucheで書かれているので、とても参考になる。

(define (cartesian-product lol)
  (if (null? lol)
      (list '())
      (let ((l (car lol))
            (rest (cartesian-product (cdr lol))))
        (append-map!
         (lambda (x)
           (map (lambda (sub-prod) (cons x sub-prod)) rest))
         l))))