12/04/08 17:02:45.73
>>55
そうは言っても関数型言語での記述は、仕様をそのまま記述してるだけだしな・・・
クイックソートの記述が有名だけど、マージソートはもっと仕様そのまま書いてるだけなのがハッキリする
-- ソート済みのリストの小さい方をリストに追加して、他方を元のリストに戻して、リストのどちらかが空になるまで比較とリストへの追加、他方のさし戻しを繰り返す
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) | x < y = x:merge xs (y:ys)
merge (x:xs) (y:ys) = y:merge (x:xs) ys
-- １要素または空になるまで半分に分割を繰り返してからmergeによる結合（１要素のリスト、または空リストはソート済みのリスト）
mergesort [] = []
mergesort [z] = [z]
mergesort zs = merge (mergesort xs) (mergesort ys)
where
(xs,ys) = splitAt (length zs `div` 2) zs
分析については、プログラミングHaskellの最後の方に書いてるプログラムの論証を読むと参考になると思う
>>41も、設計もへったくれも無く、こうしたいなと言う脳内仕様をそのまま書いたし、checkPermuを外に追い出して差し替えられるようにしたいな。とか、長さの異なるリストも扱えるようにしたいな。という気まぐれでどんどん変更してた
（そもそも設計が必要な規模じゃないが)