ストリームの要素からn要素を選ぶ順列のストリーム

perm.ml

let rec interleave xs ys () =
  match xs () with
  | Seq.Nil -> ys ()
  | Seq.Cons (x, xs) -> Seq.Cons (x, interleave ys xs)

let rec perm_aux n s0 s xs () =
  if n <= 0
  then Seq.return xs ()
  else
    match s () with
    | Seq.Nil -> Seq.Nil
    | Seq.Cons (x, s') ->
        interleave
          (perm_aux (n - 1) Fun.id (s0 s') (x :: xs))
          (perm_aux n (fun s -> s0 (Seq.cons x s)) s' xs) ()

(* 与えられたストリームからn要素を選ぶ順列を列挙 *)
let perm : int -> 'a Seq.t -> 'a list Seq.t = fun n s -> perm_aux n Fun.id s []

(* 自然数のストリーム *)
let rec nats n () = Seq.Cons (n, nats (n + 1))
let nats = nats 0

(* ストリームの先頭からn要素をリストにして取り出す *)
let rec take n xs =
  match xs () with
  | Seq.Nil -> []
  | Seq.Cons (x, xs) -> if n <= 0 then [] else x :: take (n - 1) xs

take 100 @@ perm 3 nats;;