(*** Finitely-branching trees ***) datatype 'a FBtree = node of 'a * 'a FBtree list ; val mytree = node(0, [node(2, [node(3,[]), node(7,[]), node(5,[])]), node(9,[]), node(10,[])]) ; val mytree1 = node(0, [node(2, [node(4, [node(1,[])]), node(8,[]), node(6,[])]), node(8, [node(11,[]), node(13,[])]), node(10,[])]) ; (*** Breadth-first search ***) fun bfs P t = let fun auxbfs [] = NONE | auxbfs( node(n,F)::T ) = if P n then SOME n else auxbfs( T @ F ) ; in auxbfs [t] end ; bfs (fn x => x mod 2 = 1) mytree ; bfs (fn x => false) mytree ; bfs (fn x => x mod 2 = 1) mytree1 ; (*** Depth-first search ***) fun dfs P t = let fun auxdfs [] = NONE | auxdfs( node(n,F)::T ) = if P n then SOME n else auxdfs( F @ T ) ; in auxdfs [t] end ; dfs (fn x => x mod 2 = 1) mytree ; dfs (fn x => false) mytree ; (*** Version without append ***) fun dfs' P t = let fun auxdfs( node(n,F) ) = if P n then SOME n else foldl (fn(t,r) => case r of NONE => auxdfs t | _ => r) NONE F ; in auxdfs t end ; dfs' (fn x => x mod 2 = 1) mytree ; dfs' (fn x => false) mytree ; (*** Version without append; raising an exception when successful ***) fun dfs0 P (t: 'a FBtree) = let exception Ok of 'a; fun auxdfs( node(n,F) ) = if P n then raise Ok n else foldl (fn(t,_) => auxdfs t) NONE F ; in auxdfs t handle Ok n => SOME n end ; dfs0 (fn x => x mod 2 = 1) mytree ; dfs0 (fn x => false) mytree ; dfs (fn x => x mod 2 = 1) mytree1 ; dfs0 (fn x => x mod 2 = 1) mytree1 ;