<< Demo041 >> << Section 5.1: Depth-first Search >> type State = term; type Goal = State; type Path = term; << = sequence >> type Solution = Path; State & Path => Path; << sequence operation >> nil = null(Path); DepthFirst(State, Goal, Path) -> multi(Solution); DepthFirst(aGoal, aGoal, aPath) = aGoal & aPath; DepthFirst(aState, aGoal, aPath) = [ NewState = NextMove(aState); DepthFirst(NewState, aGoal, aState & aPath) when ~ member(NewState, aPath)]; type element = State; type sequence = Path; member(element, sequence) -> boolean; member(X,=nil) = false; member(X, X & Tail) = true; member(X, Head & Tail) = member(X,Tail); NextMove(State) -> multi(State); NextMove(state(L1,L2,L3)) = (state(L2,L1,L3), state(L3,L2,L1), state(L1,L3,L2)); type letter = term; state(letter,letter,letter) => State; A,B,C => letter; DepthFirst(state(A,B,C), state(C,B,A), nil)? << Depth-first search with Depth limitation >> DepthFirst(State, Goal, Path, Depth=integer) -> multi(Solution); DepthFirst(aGoal, aGoal, aPath, Depth) = aGoal & aPath; DepthFirst(aState, aGoal, aPath, Depth) = [ NewState = NextMove(aState); DepthFirst(NewState, aGoal, aState & aPath, Depth-1) when ~ member(NewState, aPath) & Depth > 1]; DepthFirst(state(A,B,C), state(C,B,A), nil, 4)?