我对用于计算一元运算符下的容器闭包的高效函数算法(最好在 Haskell 中,甚至更优选已经作为库的一部分实现!)感兴趣。
对于列表,我想到的一个基本且低效的示例是:
closure :: Ord a => (a -> a) -> [a] -> [a]
closure f xs = first_dup (iterate (\xs -> nub $ sort $ xs ++ map f xs) xs) where
first_dup (xs:ys:rest) = if xs == ys then xs else first_dup (ys:rest)
更有效的实现会跟踪每个阶段(“边缘”)生成的新元素,并且不会将该函数应用于已应用的元素:
closure' :: Ord a => (a -> a) -> [a] -> [a]
closure' f xs = stable (iterate close (xs, [])) where
-- return list when it stabilizes, i.e., when fringe is empty
stable ((fringe,xs):iterates) = if null fringe then xs else stable iterates
-- one iteration of closure on (fringe, rest); key invariants:
-- (1) fringe and rest are disjoint; (2) (map f rest) subset (fringe ++ rest)
close (fringe, xs) = (fringe', xs') where
xs' = sort (fringe ++ xs)
fringe' = filter (`notElem` xs') (map f fringe)
例如,如果xs
是 的非空子列表[0..19]
,closure' (\x->(x+3)`mod`20) xs
则为 [0..19],并且迭代稳定在 20 步[0]
、13 步[0,1]
和 4 步[0,4,8,12,16]
。
使用基于树的有序集实现可以获得更高的效率。这已经完成了吗?在二元(或更高元数)运算符下的闭包相关但更难的问题呢?