% $Id: Sorted.oz,v 1.1 2007/11/26 21:06:53 leavens Exp leavens $ declare % description of relationships proc {Sorted InList ?OutList} {Permutation InList OutList} %% and {Ordered OutList} end proc {Permutation InList ?OutList} choice nil=InList OutList=nil [] X Xs PXs N Pos in X|Xs=InList {Permutation Xs PXs} N={Length PXs} %% make an N+1-way choice point Pos={Space.choose N+1} %% insert X at each place in PXs OutList={InsertBefore PXs Pos X} end end fun {InsertBefore Ls Pos X} % requires Pos is a legal index of Ls Prefix Suffix in {List.takeDrop Ls Pos-1 Prefix Suffix} {Append Prefix X|Suffix} end proc {Ordered Ls} case Ls of nil then skip [] _|nil then skip [] X|Y|Zs then (X =< Y)=true {Ordered Y|Zs} end end