Потенциал для оптимизации наборов для перечисления пространства состояний в Haskell на основе профиля кучи?

Question

Я написал небольшой проводник пространства состояний для исчерпывающей проблемы поиска.Учитывая начальное состояние, переходное отношение вычисляет набор состояний-преемников, пока все состояния не будут видны (я знаю, что пространство поиска конечно).Для моей проблемы это приводит к 2 * n вершинам состояний преемника.Для всех состояний я также проверяю, удовлетворяют ли они некоторому свойству dlCheck (здесь во всем пространстве состояний есть только ОДНО соответствующее состояние).

Поскольку я сохраняю Data.Set видимых состояний вокруг, яЯ ожидаю большого потребления памяти.Однако профиль кучи меня озадачивает (ATest содержит приведенный ниже код, проверка свойств и переход находятся в другом модуле):

Если бы я догадался, я бы сказал, что нижняя границаSet - размер уже исследованного пространства состояний. Мне интересно, откуда происходит периодическое сокращение. Вы заметили что-нибудь смешное в исследовании ниже?Основной вызов находится в конце dlsStreamHist внизу.

Учитывая, что вся программа слишком велика для публикации, и у меня есть некоторое представление о производительности отношения перехода и проверке свойств, я 'м при условии, что проблема где-то здесь.Возможно, я ищу строгие операции над множествами, очень похожие на foldl'?Может быть так, что сначала все состояния преемника вычисляются, прежде чем сравнивать их с набором seen, вместо того, чтобы делать это на лету.

-- 'test' applies a step to each process in the state (individually), yielding a set of successor states
-- ...or not, if a process blocks. Already seen states are in the first component
-- so that we don't explore them again,
-- blocked configs go into the second, and new successor states go into the third component.
-- We produce a potentially infinite stream of sets of blocked/enabled configurations.
-- This method generates our search space; the transition relation 'step' is in here.
testHistory :: State a => Set a -> Set a -> [(Set a, Set a, Set a)]
testHistory seen ps
  | null ps = []
  | otherwise = let (ls,rs) = fold (\s lr -> fold (\x (l,r) -> maybe (insert s l,r)
                                                                     (\c -> (l,insert c r)) x) lr (step s)) (empty,empty) ps
                    newSeen = seen `union` ps
                    new = rs `difference` newSeen
                    in (newSeen,ls,new):(testHistory newSeen new)

-- Take a program, and run it (to infinity). For each blocked configuration, collect all deadlocks (if any).
-- For infinite streams, you might want to 'nub' the result.
dlsStreamT :: State a => (Set a -> [(Set a, c)]) -> a -> [Set (Process,Lock,Int)]
dlsStreamT testF p = concatMap (Data.Set.toList . (fold (union) empty) . (filter (not . null)) . (Data.Set.map (filter (not . null)))) $ map ((filter (not . null)) . (Data.Set.map dlCheck) . fst) (testF (singleton p))
dlsStreamHist :: State a => a -> [Set (Process,Lock,Int)]
dlsStreamHist = dlsStreamT (map (\(_,x,y)->(x,y)) . testHistory empty)

Answer 1

По-видимому, ему нужно создать целый набор новых состояний, прежде чем он сможет завершить каждый шаг testHistory: вы не можете вычислить rs `difference` newSeen, пока не построите, например, все newSeen (по понятным причинам ).

Тогда я бы предположил, что фильтрация по dlCheck является ленивой, поэтому он собирает кучу громов, прежде чем оценивать их все, что приводит к использованию пульсирующей кучи. Есть ли какая-то причина, по которой вы не можете сложить dlCheck в генерацию состояний, чтобы можно было применять ее к состояниям по мере их создания?

NB, какую алгебру процессов вы используете? (Не то чтобы это уместно, это просто мое поле!)