Утечка пространства рекурсии Haskell

[Обновлять]

Поэтому я изменил свой код, чтобы сделать его более читаемым. У функции dpfsSat два аргумента, klauselMenge — это огромный набор с элементами из X. Во время рекурсии klauselMenge должен сокращаться через какие-то функции.

import qualified Data.IntSet as Set
import qualified Data.IntMap as IntMap
import qualified Data.Vector as V

data X
    = Xin !(Int,(Set.IntSet)) deriving (Eq,Show,Ord)

type Klausel = [Atom]
type KlauselMenge = [Klausel]

dpfsSat :: Int -> KlauselMenge -> Klausel
dpfsSat fset klauselMenge = dpfsSat' fset klauselMenge []
  where
   dpfsSat' :: Int -> KlauselMenge -> Klausel -> Klausel
   dpfsSat' _ [] l = resolveDuplicateLiterals l
   dpfsSat' f k l
    | f `seq` k `seq` l `seq` False = undefined
    | [] `elem` k = []
    | ok1 = dpfsSat' f rTF l
    | ok2 = dpfsSat' f (substituteSimilarUnits (atomToTupel v2) k) l
    | ok3 = dpfsSat' f (resolveUnit1 v3 k ) ((Xin v3):l)
    | ok4 = dpfsSat' f (resolvePureLiteral v4 k) ((Xin v4):l)
    | otherwise = case (dpfsSat' f (resolveUnit1 minUnit k) ((Xin minUnit): l)) of
          [] -> dpfsSat' f ( resolveUnit1 kompl k)  ((Xin kompl): l)
          xs -> xs
    where
 rTF = resolveTrueFalse f v1 k
 minUnit = findBestLiteral4 k
 kompl   = (fst minUnit,Set.difference (Set.fromList [1..f]) (snd minUnit))
 fTF = findTrueFalse4 f k
 fSU = findSimilarAtomUnits f k
 fU  = findUnit' k
 fP  = findPureLiteral k
 ok1 = maybeToBool fTF
 ok2 = maybeToBool fSU
 ok3 = maybeToBool fU
 ok4 = maybeToBool fP
 v1  = expectJust fTF
 v2  = expectJust fSU
 v3  = expectJust fU
 v4  = expectJust fP

maybeToBool :: Maybe a -> Bool
maybeToBool (Just x) = True
maybeToBool Nothing  = False

expectJust :: Maybe a -> a
expectJust (Just x) = x
expectJust Nothing  = error "Unexpected Nothing" 

Поскольку мне не разрешено загружать изображения, я записываю вывод профиля кучи (-hy). Куча полна IntSet.


person tomic84    schedule 07.02.2012    source источник
comment
Должны ли A, B, C и D быть функциями? Написание их в верхнем регистре делает их похожими на конструкторы. И как X актуально?   -  person dave4420    schedule 07.02.2012
comment
Простите за это. A, B, C и D — функции. Конструктор X нужен для некоторого возможного другого представления.   -  person tomic84    schedule 07.02.2012
comment
Поскольку a (c u) f l является результатом, его оценка может быть принудительно выполнена только извне a. Чтобы определить утечку, мы должны увидеть больше кода.   -  person Daniel Fischer    schedule 07.02.2012
comment
теперь я разместил еще немного кода. Что вы имеете в виду оценка может только силой извне?   -  person tomic84    schedule 07.02.2012
comment
Знаете ли вы, что подобные конструкции case могут быть написаны гораздо менее неудобным образом с использованием защиты шаблонов ? И в примере кода, который у вас есть сейчас, что это за a (c u) f l?   -  person leftaroundabout    schedule 07.02.2012
comment
Правильно ли я понимаю: в findTrueFalse вы приводите список concat xs к Data.Vector только для того, чтобы O (1) найти в нем элемент, удовлетворяющий предикату fT?? Это выглядит невероятно контрпродуктивным, просто выполнение этого поиска в списке напрямую должно быть быстрее, чем приведение только к Vector, и он вообще не выделяет никакого места, как вы должны для этого вектора!   -  person leftaroundabout    schedule 07.02.2012
comment
Когда «его оценка может быть принудительно выполнена только извне a», я имею в виду, что вы не можете заставить функцию полностью оценить свой результат изнутри функции, он будет оцениваться только тогда, когда что-то вне функции должно оценить результат. Вы можете сделать так, чтобы он полностью оценивался, если что-то внешнее требует только частичной оценки — let r = foo bar baz in deepseq r r — если тип результата имеет экземпляр NFData, но это не обязательно хорошая идея. Общее замечание: типы помогают, всегда ставьте сигнатуру типа на свою функцию, это помогает компилятору и читателям...   -  person Daniel Fischer    schedule 07.02.2012
comment
... И у меня сложилось впечатление, что в примере кода k - это то же самое, что и klauselMenge, верно? Можем ли мы получить компилируемый пример? Не видя реализации таких вещей, как substituteSimilarUnits, трудно догадаться, откуда может браться утечка.   -  person Daniel Fischer    schedule 07.02.2012
comment
Либо [] `elem` klauselMenge, либо нет. Если [] является элементом klauselMenge, то dpfsSat x y z оценивается как [] независимо от аргументов. Если это не так, то условие никогда не выполняется, и мы всегда переходим к otherwise: но если ghc не может понять это, ему приходится вычислять истинное значение [] `elem` klauselMenge каждый раз, когда он делает рекурсивный шаг.   -  person applicative    schedule 08.02.2012
comment
По сути, у меня есть огромный список (с именем k) с элементами конструктора X. Теперь есть некоторые функции, такие как replaceSimilarUnits или resolveUnit, которые пытаются упростить (или уменьшить) k посредством рекурсии. Аргумент l хранит элементы, которые я удалил из k, и представляет результат.   -  person tomic84    schedule 08.02.2012
comment
... все функции, особенно findTrueFalse, выполняются в константном пространстве   -  person tomic84    schedule 08.02.2012
comment
Вынуждает ли ваша функция resolveUnit1 свой первый аргумент kompl и насколько глубоко? Простое сопоставление с образцом не заставит его составляющие, так как это пара. kompl также держится за пару minUnit, поэтому, возможно, у него может быть утечка пространства в паре Вадлера.   -  person Will Ness    schedule 11.02.2012
comment
между прочим, ваш maybeToBool точно такой же, как isJust, а ваш expectJust почти такой же (вплоть до сообщения об ошибке), что и fromJust, функционирующий из Data.Maybe.   -  person Will Ness    schedule 11.02.2012


Ответы (1)


Если c похоже на (1+), то это может привести к утечке, поскольку вы создаете цепочку переходников (1+(1+(1+...))). Чтобы избежать этого, используйте seq:

let k' = c u in k' `seq` a k' f l

seq заставит вычислить k' до того, как можно будет оценить a k' f l, так что во многих случаях это устранит утечку пространства.

Однако seq не является панацеей, и вы должны прочитать о его правильном использовании и избегайте неправильного использования.

person rampion    schedule 07.02.2012
comment
в этом случае функция c вычисляет новый список, возможно меньший - person tomic84; 09.02.2012
comment
@tomic84: tomic84: это все еще может привести к тому, что цепочка переходников создаст (c (c (c (c (c ... ))))), поскольку значение u никогда не форсируется до того, как оно будет передано. - person rampion; 09.02.2012
comment
Для меня это имеет смысл, но попытка форсировать оценку с помощью seq не меняет утечку кучи. - person tomic84; 09.02.2012