<< Demo042 >> << Section 5.2: Breadth-first search >> type State = term; type Goal = State; type Path = term; << = sequence >> type Solution = Path; State & Path => Path; << sequence operation >> nil = null(Path); BreadthFirst(State, Goal) -> multi(Solution); BreadthFirst(Start, aGoal) = [ Queue = { Start & nil }; [ aPath = items(Queue); aState = State(aPath); if aState <> aGoal then [ NewState = NextMove(aState); add(Queue, NewState & aPath) when ~ member(NewState,aPath)] else result(aPath) ]; no(Solution)]; State(Path) -> State; State(State & Path) = State; 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; BreadthFirst( state (A, B, C), state (C, B, A))?