読者です 読者をやめる 読者になる 読者になる

osiire’s blog

ふしぎなそふとやさん

幅・深さ優先fold

思いつきで書いているので、全く当てになりません。あしからず。

type 'a t = {
    dat : 'a;
    children : 'a t list;
  }

let bff f x t =
  let q = 
    Queue.create ()
  in
  Queue.add t q;
  let rec loop r =
    try
      let t =
	Queue.pop q
      in
      List.iter (fun c -> Queue.push c q) t.children;
      loop (f r t.dat)
    with
      Queue.Empty -> 
	r
  in
  loop x
    
let rec dff f x t =
  List.fold_left (fun r c -> dff f r c) (f x t.dat) t.children