On Dec 4, 2007 10:00 PM, Neil Mitchell
Hi
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 in all call paths findAllPath will call g with its second argument. g will always evaluate (by pattern matching on) its value argument.
Wait! You're analyzing my second function and you're saying that it is strict in its arguments? Gee, that's bad. I questioned about the first one. The second seems to be definitely lazy because I can use it on such big trees like I showed. How come I can do this computation if like you said the function is strict?
2 - if it really is strict in its arguments, is there any automated way to know when a function is strict in its arguments?
Yes, strictness analysis is a very well studied subject - http://haskell.org/haskellwiki/Research_papers/Compilation#Strictness . Essentially, an argument is strict if passing _|_ for that value results in _|_. So to take your example, evaluating:
findAllPath a _|_ g _|_ _|_
Since g tests what value _|_ has, we get bottom.
Thanks
Neil
-- Paulo Jorge Matos - pocm at soton.ac.uk http://www.personal.soton.ac.uk/pocm PhD Student @ ECS University of Southampton, UK