2014/05/18

リストを交互に分配

お題: (リストを交互に分配) - 　分室の分室

分かり易い題名が浮かばなかった。やりたいのは、こういうこと。

(x0 y0 x1 y1 x2 y2) → ((x0 x1 x2) (y0 y1 y2))

Schemeなんだからリスト処理は得意…のはずなんだけれど、

• 繰り返しごとに複数の要素を消費する
• 繰り返しごとに複数の値を蓄積する

といった問題に使えるツールは、標準やsrfiにいまいち揃ってない印象がある。

Gaucheの場合はslicesが手軽。ワンライナーでいける。

(define (alternate1 lis)
  ($ apply map list $ slices lis 2))

但しこれは一度中間リスト((x0 y0) (x1 y1) (x2 y2))を作る。 それを嫌うなら遅延シーケンス。applyを使うと適用前にシーケンスを現実化してしまうので、 srfi-1のunzip2を使おう。

(use gauche.lazy)
(use srfi-1)

(define (alternate2 lis)
  ($ values->list $ unzip2 $ lslices lis 2))

(実はlazy版のlslicesはこのエントリを書きながら気づいて足したので HEADのGaucheでないと使えない。)

標準だけ使う縛りの場合は、素直に再帰するのが結局は一番簡単になるような気がする。

(define (alternate3 lis)
  (let loop ([lis lis] [xs '()] [ys '()])
    (if (null? lis)
      (list (reverse xs) (reverse ys))
      (loop (cddr lis) (cons (car lis) xs) (cons (cadr lis) ys)))))

consしていってreverse、というパターンはリストを一回余分にコピーするので 無駄なようだが、多くの場合、アクセスのローカリティは高いしそれほど気になることはない。 入力の長さが短くて、集める値がひとつだけの場合は非末尾再帰で書いてreverseを省く、 という手はあるのだけれど、集める値が複数だと多値を持ち回るのでそれほどわかりやすくならない。 (集める値が2系統だが、繰り返しごとにひとつの値だけを消費する、という場合は fold2が使えるんだけど)。

この点、Common Lispのloopは柔軟だ。

(defun alternate-l (lis)
  (loop for (x y) on lis by #'cddr
    collect x into xs 
    collect y into ys 
    finally (return (list xs ys))))

loop の仕様はひどくごちゃごちゃして見えるけど、いろんなケースに対応できるように 考えられてはいる。

Tags: Gauche, Scheme