大人げ

http://d.hatena.ne.jp/soutaro/20070516/1179323606

に脊髄反射。

open Lazy

type tree = S of string | Or of tree lazy_t * tree lazy_t

let rec map f = function
  | S s -> S (f s)
  | Or(l, r) -> Or(lazy (map f (force l)),
                   lazy (map f (force r)))

let rec prod = function
  | S s, t -> map (fun s' -> s ^ s') t
  | Or(l, r), t -> Or(lazy (prod (force l, t)),
                      lazy (prod (force r, t)))

let rec rep t =
  Or(lazy (S ""),
     lazy (prod (t, rep t)))

let rec bfs n q =
  if n <= 0 then [] else
  match q with
  | [] -> []
  | S s :: q' -> s :: bfs (n - 1) q'
  | Or(l, r) :: q' -> bfs n (q' @ [force l; force r])

type re =
  | Lit of string
  | Cat of re * re
  | Alt of re * re
  | Rep of re

let rec gen = function
  | Lit s -> S s
  | Cat(e1, e2) -> prod (gen e1, gen e2)
  | Alt(e1, e2) -> Or(lazy (gen e1), lazy (gen e2))
  | Rep e -> rep (gen e)

# let e1 = Alt(Lit "0", Lit "1") ;;
val e1 : re = Alt (Lit "0", Lit "1")
# let e2 = Lit "_" ;;
val e2 : re = Lit "_"
# let e = Cat(e1, Cat(e2, Cat(e1, e2))) ;;
val e : re =
  Cat (Alt (Lit "0", Lit "1"),
   Cat (Lit "_", Cat (Alt (Lit "0", Lit "1"), Lit "_")))
# bfs 100 [gen (Rep e)] ;;
- : string list =
[""; "0_0_"; "0_1_"; "1_0_"; "1_1_"; "0_0_0_0_"; "0_0_0_1_"; "0_0_1_0_";
 "0_0_1_1_"; "0_1_0_0_"; "0_1_0_1_"; "0_1_1_0_"; "0_1_1_1_"; "1_0_0_0_";
 "1_0_0_1_"; "1_0_1_0_"; "1_0_1_1_"; "1_1_0_0_"; "1_1_0_1_"; "1_1_1_0_";
 "1_1_1_1_"; "0_0_0_0_0_0_"; "0_0_0_0_0_1_"; "0_0_0_0_1_0_"; "0_0_0_0_1_1_";
 "0_0_0_1_0_0_"; "0_0_0_1_0_1_"; "0_0_0_1_1_0_"; "0_0_0_1_1_1_";
 "0_0_1_0_0_0_"; "0_0_1_0_0_1_"; "0_0_1_0_1_0_"; "0_0_1_0_1_1_";
 "0_0_1_1_0_0_"; "0_0_1_1_0_1_"; "0_0_1_1_1_0_"; "0_0_1_1_1_1_";
 "0_1_0_0_0_0_"; "0_1_0_0_0_1_"; "0_1_0_0_1_0_"; "0_1_0_0_1_1_";
 "0_1_0_1_0_0_"; "0_1_0_1_0_1_"; "0_1_0_1_1_0_"; "0_1_0_1_1_1_";
 "0_1_1_0_0_0_"; "0_1_1_0_0_1_"; "0_1_1_0_1_0_"; "0_1_1_0_1_1_";
 "0_1_1_1_0_0_"; "0_1_1_1_0_1_"; "0_1_1_1_1_0_"; "0_1_1_1_1_1_";
 "1_0_0_0_0_0_"; "1_0_0_0_0_1_"; "1_0_0_0_1_0_"; "1_0_0_0_1_1_";
 "1_0_0_1_0_0_"; "1_0_0_1_0_1_"; "1_0_0_1_1_0_"; "1_0_0_1_1_1_";
 "1_0_1_0_0_0_"; "1_0_1_0_0_1_"; "1_0_1_0_1_0_"; "1_0_1_0_1_1_";
 "1_0_1_1_0_0_"; "1_0_1_1_0_1_"; "1_0_1_1_1_0_"; "1_0_1_1_1_1_";
 "1_1_0_0_0_0_"; "1_1_0_0_0_1_"; "1_1_0_0_1_0_"; "1_1_0_0_1_1_";
 "1_1_0_1_0_0_"; "1_1_0_1_0_1_"; "1_1_0_1_1_0_"; "1_1_0_1_1_1_";
 "1_1_1_0_0_0_"; "1_1_1_0_0_1_"; "1_1_1_0_1_0_"; "1_1_1_0_1_1_";
 "1_1_1_1_0_0_"; "1_1_1_1_0_1_"; "1_1_1_1_1_0_"; "1_1_1_1_1_1_";
 "0_0_0_0_0_0_0_0_"; "0_0_0_0_0_0_0_1_"; "0_0_0_0_0_0_1_0_";
 "0_0_0_0_0_0_1_1_"; "0_0_0_0_0_1_0_0_"; "0_0_0_0_0_1_0_1_";
 "0_0_0_0_0_1_1_0_"; "0_0_0_0_0_1_1_1_"; "0_0_0_0_1_0_0_0_";
 "0_0_0_0_1_0_0_1_"; "0_0_0_0_1_0_1_0_"; "0_0_0_0_1_0_1_1_";
 "0_0_0_0_1_1_0_0_"; "0_0_0_0_1_1_0_1_"; "0_0_0_0_1_1_1_0_"]

何か間違ってたら直してください（他力本願）。

追記：要するにランダムじゃなくて順に列挙できるという話です。一応。

っていうかHaskellで書くべきなのですが、文法を暗記していないのでよろしくお願いします（何をだ）。＞詳しい方　もちろん、JavascriptやRubyでも書けます。（僕は書けませんが…）

あと、実は左のlazyはいらないです。

追記２：syd_sydさんによるHaskell版。

追記３：よく見たらmapは一回しか使っていないので、prodに混ぜれば不要だった。気づけよ！＞自分

let rec prod = function
  | S s, S s' -> S(s ^ s')
  | Or(l, r), t -> Or(lazy (prod (force l, t)),
                      lazy (prod (force r, t)))
  | t, Or(l, r) -> Or(lazy (prod (t, force l)),
                      lazy (prod (t, force r)))