CODEWITHSUNDEEP
haskelllazy-evaluationbinary-search-tree
clintm
clintm

Reputation: 1259

Determining the extent of lazy evaluation

Given

data BTree a = End
             | Node a (BTree a) (BTree a)
   deriving(Show,Eq,Ord)

data Msg = Msg { from :: String
               , to :: String
               , when :: Int
               , message :: String }

instance Ord Msg where
    compare a b = (when a) `compare` (when b)

instance Eq Msg where
    (==) a b = (when a) == (when b)

My function to count nodes (which seems off but that's aside from the question) is

count :: (Ord a) => (BTree a) -> Int
count = sum . count'
 where
  count' :: (Ord a) => (BTree a) -> [Int] 
  count' End = []
  count' (Node _ l r) =
    [1] ++ (count' l) ++ (count' r)

Does count not evaluate the contents of the Msg by virtue of its value being discarded by _? Perhaps a better question is, how do I know where lazy evaluation starts and ends for this sort of thing?

If the third line of count' was:

count' (Node (Msg x _ _ _) l r) =

Can I assume that the other three fields of Msg were accessed/evaluated, or does lazy evaluation go that far?

Upvotes: 1

Views: 122

Answers (1)

hammar
hammar

Reputation: 139840

No. The fields of a data structure are evaluated lazily by default. Since you're not using the other fields in any way, they will not be evaluated by this code. If you want to make it so that evaluating a node forces all its fields to be evaluated, you can add strictness annotations to the fields:

data BTree a = End
             | Node !a (BTree a) (BTree a)
   deriving(Show,Eq,Ord)

data Msg = Msg { from :: !String
               , to :: !String
               , when :: !Int
               , message :: !String }

Since counting the nodes forces the nodes themselves to be evaluated, this will also force the node values to be evaluated. If you only want this behavior for your one function, you can force evaluation in a more fine-grained manner using seq:

count' (Node x l r) = x `seq` ([1] ++ count' l ++ count' r)

or a bang pattern (requires the BangPatterns extension)

count' (Node !x l r) = [1] ++ count' l ++ count' r

Upvotes: 1

Related Questions