高效的函数算法用于计算运算符下的闭包

Question

高效的函数算法用于计算运算符下的闭包

9

我很感兴趣的是高效的函数式算法（最好是在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]，并且对于[0]，迭代稳定在20步，对于[0,1]，迭代稳定在13步，对于[0,4,8,12,16]，则迭代稳定在4步。

使用基于树的有序集合实现，可以进一步提高效率。这个是否已经完成了？而对于二元（或更高元）运算符下的闭包，相关但更难的问题是什么？

- lambdacalculator

懒惰有关系吗？ - Daniel Wagner

不在我考虑的应用程序中，我的有限集已经是封闭的，我想计算子集的闭包。 - lambdacalculator

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- J. Abrahamson · Accepted Answer

使用哈希数组映射字典树数据结构，可以像这样实现，其中使用了unordered-containers库。对于unordered-containers库中的member和insert操作，时间复杂度为O(min(n,W))，其中W是哈希值的长度。

module Closed where

import Data.HashSet (HashSet)
import Data.Hashable
import qualified Data.HashSet as Set

data Closed a = Closed { seen :: HashSet a, iter :: a -> a } 

insert :: (Hashable a, Eq a) => a -> Closed a -> Closed a
insert a c@(Closed set iter)
  | Set.member a set = c
  | otherwise        = insert (iter a) $ Closed (Set.insert a set) iter

empty :: (a -> a) -> Closed a
empty = Closed Set.empty

close :: (Hashable a, Eq a) => (a -> a) -> [a] -> Closed a
close iter = foldr insert (empty iter)

这是上面方法的一种变化，以广度优先的方式更懒地生成解决方案集。

data Closed' a = Unchanging | Closed' (a -> a) (HashSet a) (Closed' a)

close' :: (Hashable a, Eq a) => (a -> a) -> [a] -> Closed' a
close' iter = build Set.empty where
  inserter :: (Hashable a, Eq a) => a -> (HashSet a, [a]) -> (HashSet a, [a])
  inserter a (set, fresh) | Set.member a set = (set, fresh)
                          | otherwise        = (Set.insert a set, a:fresh)
  build curr [] = Unchanging
  build curr as =
    Closed' iter curr $ step (foldr inserter (curr, []) as)
  step (set, added) = build set (map iter added)

-- Only computes enough iterations of the closure to 
-- determine whether a particular element has been generated yet
-- 
-- Returns both a boolean and a new 'Closed'' value which will 
-- will be more precisely defined and thus be faster to query
member :: (Hashable a, Eq a) => a -> Closed' a -> (Bool, Closed' a)
member _ Unchanging = False
member a c@(Closed' _ set next) | Set.member a set = (True, c)
                                | otherwise        = member a next

improve :: Closed' a -> Maybe ([a], Closed' a)
improve Unchanging = Nothing
improve (Closed' _ set next) = Just (Set.toList set, next)

seen' :: Closed' a -> HashSet a
seen' Unchanging = Set.empty
seen' (Closed' _ set Unchanging) = set
seen' (Closed' _ set next)       = seen' next

并且进行检查

>>> member 6 $ close (+1) [0]
...

>>> fst . member 6 $ close' (+1) [0]
True