[Haskell-cafe] Comments and suggestions on code

[Jonathan Cast]

On 10 Jan 2008, at 10:21 AM, Andre Nathan wrote:

> Hi Jonathan
>
> On Wed, 2008-01-09 at 21:32 -0800, Jonathan Cast wrote:
>> An actual coding question, abuse?  We should be so lucky.
>
> :) Your comments are much appreciated.

You're welcome.

>> This function is fairly complicated, simply because of the number of
>> separate definitions involved; I would be looking for opportunities
>> to inline definitions here, so it's clearer what the definitions
>> are.  (Also, I would try to build a single, self-recursive function
>> at the top level, put the call to procInfo there, and make everything
>> else pure).
>
> I rewrote insertInTree like below. Now it is the only function that  
> has
> a StateT return type, and I also got rid of addProc, insertPid and
> insertParent :)
>
> insertInTree :: Pid -> StateT PsTree IO ()
> insertInTree pid = do
>   tree <- get
>   if Map.member pid tree
>     then return ()
>     else do
>       info <- lift $ procInfo pid
>       modify (Map.insert pid info)
>       let ppid = parentPid info
>       if ppid /= "0"
>         then do
>           insertInTree ppid
>           modify (appendChild ppid pid)
>         else return ()
>
> I also rewrote createTree like this:
>
> createTree :: IO PsTree
> createTree = do
>   entries <- getDirectoryContents "/proc"
>   let procs = filter (=~ "^[0-9]+$") entries
>   execStateT (mapM_ insertInTree procs) Map.empty
>
> Is that a bad way to do it? If haskell wasn't lazy this would be 3 O 
> (n)
> operations, and I could write it using readDirStream to process all
> entries in one pass.  I'm not sure if that's really necessary when
> laziness is present though.

It might be faster; laziness usually has higher constants than direct  
implementations.  But I doubt the difference is critical in this  
case, and I would definitely time a re-writing and throw it away  
unless it was significantly faster.  But I don't think this is a case  
where laziness actually alters either the time or the space  
asymptotics of the algorithm (you end up creating an ~ O(n) tree  
anyway, so I'd figure O(n) space was OK for the loop, too).

jcc