On Tue, Dec 04, 2007 at 09:41:36PM +0000, Paulo J. Matos wrote:
Hello all,
As you might have possibly read in some previous blog posts: http://users.ecs.soton.ac.uk/pocm06r/fpsig/?p=10 http://users.ecs.soton.ac.uk/pocm06r/fpsig/?p=11
we (the FPSIG group) defined: data BTree a = Leaf a | Branch (BTree a) a (BTree a)
and a function that returns a list of all the paths (which are lists of node values) where each path element makes the predicate true. findAllPath :: (a -> Bool) -> (BTree a) -> Maybe [[a]] findAllPath pred (Leaf l) | pred l = Just [[l]] | otherwise = Nothing findAllPath pred (Branch lf r rt) | pred r = let lfpaths = findAllPath pred lf rtpaths = findAllPath pred rt in if isNothing lfpaths && isNothing rtpaths then Nothing else if isNothing lfpaths then Just (map (r:) $ fromJust rtpaths) else if isNothing rtpaths then Just (map (r:) $ fromJust lfpaths) else Just (map (r:) $ fromJust rtpaths ++ fromJust lfpaths) | otherwise = Nothing
Later on we noticed that this could be simply written as: findAllPath :: (a -> Bool) -> (BTree a) -> [[a]] findAllPath pred = g where g (Leaf l) | pred l = [[l]] g (Branch lf r rt) | pred r = map (r:) $ (findAllPath pred lf) ++ (findAllPath pred rt) g _ = []
without even using maybe. However, 2 questions remained: 1 - why is the first version strict in its arguments?
Because of the definition of strictness. A function is strict iff f undefined = undefined. findAllPath pred undefined -> undefined because of the case analysis findAllPath undefined (Leaf _) -> undefined because pred is applied in the guard findAllPath undefined Branch{} -> undefined because pred is applied in the guard
2 - if it really is strict in its arguments, is there any automated way to know when a function is strict in its arguments?
No, because this is in general equivalent to the halting problem: f _ = head [ i | i <- [1,3.], i == sum [ k | k <- [1..i-1], i `mod` k == 0 ] ] f is strict iff there do not exist odd perfect numbers. However, fairly good conservative approximations exist, for instance in the GHC optimizer - compile your code with -ddump-simpl to see (among other things) a dump of the strictness properties determined. (use -O, of course) Stefan