1

Data.List.Ordered ライブラリを使用して、各要素を取得し、それに関数を適用して元の要素で結果を収集し、新しい要素がなくなるまでそれを繰り返すことで、リストを拡張する関数を表現しようとしました。作成した。さて、Data.Set を見ると、union 演算は O(n+m) で、Data.List.Ordered の nubSort は O(n) であるため、おそらく速度は向上しませんが、機能しませんでした。理由はわかりません。

import Data.List.Ordered --install data-ordlist

次の点を考慮してください。

nextimg:: Ord a => (a->a)->[a]->[a]
nextimg f x = nubSort $ union (map f x) x

ご了承ください

nextimg ((`mod` 3).(+1)) [1,2]
== nextimg ((`mod` 3).(+1)) [0,1,2]
== [0,1,2]

しかし、これを再帰的に実行しようとすると:

orbit:: Ord a => (a->a)->[a]->[a]
orbit f x = orbit f ( nubSort $ union (map f x) x )

その後、これは永久に実行されます：

orbit ((`mod` 3).(+1)) [1]
4

2 に答える 2

0

もっと細かくしたほうがいい

import Data.List.Ordered                -- install data-ordlist

next f xs = nubSort $ map f xs

それから

orbit f xs = snd $ until 
    (\(ys,xs) -> null $ minus ys xs)    -- nothing new to add
    (\(ys,xs) -> (next f $ union ys xs, ys))
    (next xs, xs)

Data.List.Ordered.union2 つの順序付きリストを呼び出すことになっています。（そしてminusあまりにも）。

于 2013-09-25T10:58:54.387 に答える