関数型プログラミング言語Haskell Part29 [転載禁止]©5ch.io
■ このスレッドは過去ログ倉庫に格納されています
0530デフォルトの名無しさん
2015/09/21(月) 13:35:14.19ID:/2p4upNw冷静に考えてみれば、いろいろ最適化できそうですね。
たとえば、unique は >>528 よりもっとシンプルになります。
巡回置換リストは、元の集合(を表したリスト)を類別します。
つまり、巡回置換リストのある要素リスト内の任意の要素は、
巡回置換リストの他の要素リスト内には存在しません。
よって、unique xs ys は elem (head xs) ys と同値です。
map nub では、nub は要らないです。
この部分の nub で要素が消えるのは、要素が繰り返し循環している部分です。
たとえば、nub [2, 3, 2, 3] = [2, 3] という感じに。
これ以外にここの nub で要素が消えるパターンはありません。
なので nub xs は、ここに限れば takeWhile (/= head xs) xs と同値です。
これで、O(n^3) から O(n^2) になりました。
せっかくなので、ひとつ残った nub をどうにかしたいところですね・・・
■ このスレッドは過去ログ倉庫に格納されています