Oz - 一般的計算モデル(宣言的プログラミング技法(クイックソート, 差分リスト))

コンピュータプログラミングの概念・技法・モデル
(IT Architect' Archive
クラシックモダン・コンピューティング6)
(IT Architects’Archive CLASSIC MODER)
(翔泳社)
セイフ・ハリディ (著), ピーター・ヴァン・ロイ (著)
Peter Van-Roy (著), Seif Haridi (著), 羽永 洋 (翻訳)
原書: Concepts, Techniques,
and Models of Computer Programming

開発環境

• OS X Yosemite - Apple (OS)
• Emacs (Text Editor)
• Oz (プログラミング言語)
• Mozartプログラミングシステム(Mozart 2) (実装)

コンピュータプログラミングの概念・技法・モデル(IT Architect' Archiveクラシックモダン・コンピューティング6) (IT Architects’Archive CLASSIC MODER)(セイフ・ハリディ (著)、ピーター・ヴァン・ロイ (著)、Peter Van-Roy (著)、 Seif Haridi (著)、羽永 洋　(翻訳) 、翔泳社、原書: Concepts, Techniques, and Models of Computer Programming(CTM))の第部(一般的計算モデル)、第3章(宣言的プログラミング技法)、3.10(練習問題)、15.(クイックソート)を解いてみる。

15.(クイックソート)

コード(Emacs)

declare
fun {Inner L X L1 L2}
   case L
   of nil then L1|L2
   [] H|T then
      if H < X then {Inner T X (H|L1) L2}
      else {Inner T X L1 H|L2}
      end
   end   
end

fun {Split L}
   case L
   of nil then nil|nil
   [] X|_ then
      {Inner L X nil nil}
   end
end

fun {AppendD D1 D2}
   S1#E1=D1
   S2#E2=D2
in
   E1=S2
   S1#E2
end

fun {Append L1 L2}
   E
in
   {AppendD L1#E E#L2}
end

fun {QuickSort L}
   if L == nil then nil
   else
      case L
      of H|nil then L
      else
         L1 L2 S1 S2
      in
         L1|L2={Split L}
         if L1 == nil then
            {QuickSort L2}
         elseif L2==nil then
            {QuickSort L1}
         else
            S1 S2
         in
            S1={QuickSort L1}
            S2={QuickSort L2}
            {Append S1 S2}
         end
      end
   end
end

{Browse {QuickSort nil}}
{Browse {QuickSort [1]}}
{Browse {QuickSort [1 2]}}
{Browse {QuickSort [2 1]}}
{Browse {QuickSort [10 1 8 3 6 5 4 7 2 9]}}