On Dec 5, 2007 1:51 PM, Luke Palmer <[EMAIL PROTECTED]> wrote: > > On Dec 4, 2007 9:41 PM, Paulo J. Matos <[EMAIL PROTECTED]> 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 > > I don't think this evaluates the whole tree every time, but it > certainly evaluates more than it needs to. It has to do with an extra > check. Here's a very operational description: > > First note that if findAllPath returns Nothing, then it has evaluated > the tree down to the contour where all the preds are false. Let's > suppose that this is the best possible case, where there is a path > down the left side of the tree with no backtracking where all nodes > are true. > > findAllPath pred (Leaf l) = Just [[l]] > > Now: > > if isNothing lfpaths && ... -- false already, lfpaths is a Just, go > to else branch > else if isNothing lfpaths ... -- false again, go to else branch > else if isNothing rtpaths ... > > To check this, you have to evaluate rtpaths down to its false contour > before you can proceed. You didn't need to do this. Instead, writing > the last else as: > > else Just (map (r:) $ fromJust lfpaths ++ fromMaybe [] rtpaths) > > Will get you behavior -- I think -- equivalent to the original. > Except for that it will return paths in leftmost order rather than > rightmost. But changing the order of some of those checks will get > you back the original rightmost behavior and lazy semantics. Left as > an exercise for the OP :-) >
Oh, ok! :) I think I got it now! Thank you! Cheers, Paulo Matos > Luke > > > 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? > > 2 - if it really is strict in its arguments, is there any automated > > way to know when a function is strict in its arguments? > > > > Cheers, > > > > -- > > Paulo Jorge Matos - pocm at soton.ac.uk > > http://www.personal.soton.ac.uk/pocm > > PhD Student @ ECS > > University of Southampton, UK > > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe@haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > > -- Paulo Jorge Matos - pocm at soton.ac.uk http://www.personal.soton.ac.uk/pocm PhD Student @ ECS University of Southampton, UK _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe