CODEWITHSUNDEEP
haskellcasetail-recursion
tomic84
tomic84

Reputation: 11

Haskell recursion space leak

[Update]

So I've changed my code to make it more readable. The function dpfsSat has two arguments, klauselMenge is a huge set with elements from X. During the recursion klauselMenge should be reduced through some functions.

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"

Since I'm not allowed to upload images, I do writing the output of the heap profile (-hy). The Heap is full of IntSet's.

Upvotes: 1

Views: 352

Answers (1)

rampion
rampion

Reputation: 89093

If c is something like (1+), then this can cause a leak as you build up a chain of thunks (1+(1+(1+...))). The way to avoid this is to use seq:

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

seq will force evaluation of k' before a k' f l can be evaluated, so this will handle the space leak in many cases.

However, seq is not a panacea, and you should read up on its proper use and avoid misusing it.

Upvotes: 1

Related Questions