Friday, June 5, 2009

Solutions to Chapter 9 (p. 228)

#1. The Info type derives Ord; and because FilePath is its first field, a list of Infos will be sorted by name. Therefore, we simply need to pass (reverse . sort) to get reverse alphabetic order.

#2. First, let's try to understand why using id yields preorder traversal. The key line in ControlledVisit.hs is bolded below:

traverse :: ([Info] -> [Info]) -> FilePath -> IO [Info]
traverse order path = do
    names <- getUsefulContents path
    contents <- mapM getInfo (path : map (path </>) names)
    liftM concat $ forM (order contents) $ \info -> do
      if isDirectory info && infoPath info /= path
        then traverse order (infoPath info)
        else return [info]

I.e., the contents to traverse is constructed as the path itself, followed by its content (loaded into names a line earlier). To change to postorder, we can modify this single line, thus:

traverse :: ([Info] -> [Info]) -> FilePath -> IO [Info]
traverse order path = do
    names <- getUsefulContents path
    contents <- mapM getInfo ((map (path </>) names) ++ [path])
    liftM concat $ forM (order contents) $ \info -> do
      if isDirectory info && infoPath info /= path
        then traverse order (infoPath info)
        else return [info]

But of course, that's not what the question is about: we should provide an order function that does this for us, rather than modify traverse directly! All this function has to do is move the first item to the list's end, so:

postorder :: [Info] -> [Info]
postorder ns = tail ns ++ [head ns]

#3. Explanations to this solution appear throughout the solution itself, as comments:

-- The InfoP type is the type of a function that
-- extracts data from an Info record:
type InfoP a = Info -> a

-- pathP extracts the path; but we already got a
-- function that does that, by virtue of Info's
-- definition as a record; so pathP is just an alias.
pathP :: InfoP FilePath
pathP = infoPath

-- For sizeP, we can't use infoSize as-is, since
-- we must handle the "Nothing" case:
sizeP :: InfoP Integer
sizeP inf = case (infoSize inf) of
              Just size -> size
              Nothing   -> -1

-- We don't really need equalP: We'll be using a lift
-- function in a minute. But it helps us formulate
-- what this lift function should look like.
equalP :: (Eq a) => InfoP a -> a -> InfoP Bool
equalP f k inf = f inf == k

-- Now, liftP abstracts the equality test from
-- equalP into any test, passed as the first argument:
liftP :: (a -> b -> c) -> InfoP a -> b -> InfoP c
liftP op f k inf = f inf `op` k

-- And we can use liftP to define greaterP, lesserP
-- (could also have used it to define equalP):
greaterP, lesserP :: (Ord a) => InfoP a -> a -> InfoP Bool
greaterP = liftP (>)
lesserP = liftP (<)
-- Note that these three definitions are identical to
-- the ones in the book (p. 223) -- but we're using
-- a different definition of liftP.

-- Now, to define andP and orP. We begin (as in the book,
-- p. 224) with simpleAndP, which helps us formulate
-- what the lifting function should look like:
simpleAndP :: InfoP Bool -> InfoP Bool -> InfoP Bool
simpleAndP f g inf = f inf && g inf

-- Let's lift the "&&" operator out of this definition:
liftP2 :: (a -> b -> c) -> InfoP a -> InfoP b -> InfoP c
liftP2 op f g inf = f inf `op` g inf

andP, orP :: InfoP Bool -> InfoP Bool -> InfoP Bool
andP = liftP2 (&&)
orP = liftP2 (||)

-- constP is almost unchanged (cf. p. 224), except
-- that our representation of an info record is a
-- single Info entry, vs. four entries in the old
-- representation:
constP :: a -> InfoP a
constP k _ = k

-- This is liftP, rewritten in terms of liftP2:
liftP' op f k inf = f inf `op` constP k

-- Lifting paths: convert a function that operates
-- on pathnames to one that operates on Info 
-- records:
liftPath :: (FilePath -> a) -> InfoP a
liftPath f = f . pathP

-- Now, the myTest2 function, as defined on p. 225,
-- should work unmodified using our new predicates
-- and combinators:
myTest2 = (liftPath takeExtension `equalP` ".cpp") `andP`
          (sizeP `greaterP` 131072)

-- To conclude, by defining infix operators, we can
-- have the definitions of myTest3 (p. 225) and myTest4
-- (p. 226), again unmodified:
(==?) = equalP
(&&?) = andP
(>?) = greaterP

myTest3 = (liftPath takeExtension ==? ".cpp") &&? (sizeP >? 131072)

infix 4 ==?
infixr 3 &&?
infix 4 >?

myTest4 = liftPath takeExtension ==? ".cpp" &&? sizeP >? 131072

#4. Because of the way traverse is defined, a directory must be part of the output if it is to be traversed. So, the traversal predicate is used to filter directories, and the filtering predicate applies to files only:

-- The first parameter is a predicate that should return true
-- only for directories that we wish to traverse. The second
-- parameter is a predicate that is used to filter files (i.e.,
-- return false for files to be removed from the output).
traverse2 :: (Info -> Bool) -> (Info -> Bool) -> FilePath -> IO [Info]
traverse2 travP filterP path = traverse (order2 travP filterP) path

order2 :: (Info -> Bool) -> (Info -> Bool) -> ([Info] -> [Info])
order2 tP fP infs = filter (\x -> (isDirectory x && tP x) || fP x) infs

Now, to find all mp3 files outside of my music directory, I can use:

traverse2 (not . liftPath (isInfixOf "Audio")) (liftPath (isInfixOf "mp3")) "c:\\"

(The liftPath function was defined in the solution to question #3 above.)

No comments:

Post a Comment