1

使用 Data.List.Ordered 库，我试图表达一个通过获取每个元素来扩展列表的函数，对其应用一个函数并将结果与​​原始元素一起收集而不重复，并重复该过程直到没有新元素创建的。现在看Data.Set，联合运算是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

1

显然，在您获得最大列表后，nubSort 对其进行排序，并且 orbit 仅“合并”已经存在的元素，并对已经排序的列表进行排序。您没有指定终止条件 - 例如，可能：

orbit f x | y == x    = x -- fixed point was found
          | otherwise = orbit f y where
            y = nubSort $ union (map f x) x
于 2013-09-25T09:12:57.100 回答
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.union两个有序列表。（minus也是）。

于 2013-09-25T10:58:54.387 回答