<br><div><span class="gmail_quote">On 10/26/07, <b class="gmail_sendername">Graham Fawcett</b> <<a href="mailto:graham.fawcett@gmail.com">graham.fawcett@gmail.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
On 10/25/07, Derek Elkins <<a href="mailto:derek.a.elkins@gmail.com">derek.a.elkins@gmail.com</a>> wrote:<br>> On Thu, 2007-10-25 at 11:30 -0400, Graham Fawcett wrote:<br>> > I'm writing a Gnu DBM module as an exercise for learning Haskell and
<br>> > its FFI. I'm wondering how I might write a function that returns the<br>> > database keys as a lazy list.<br>> Just use unsafeInterleaveIO in the obvious definition to read all the<br>> keys. That said, it's not called unsafeInterleaveIO for no reason.
<br><br>I got it to work, using unsafeInterleaveIO. Thanks! But I suspect I<br>might be working too hard to get the result. Is anyone willing to<br>critique my code?<br><br>Given firstKey and nextKey:<br><br> firstKey :: DbP -> IO (Maybe String)
<br> nextKey :: DbP -> String -> IO (Maybe String)<br><br>I wrote these eager and lazy key-iterators:<br><br> allKeys :: DbP -> IO [String]<br> allKeys = traverseKeys id<br><br> unsafeLazyKeys :: DbP -> IO [String]
<br> unsafeLazyKeys = traverseKeys unsafeInterleaveIO<br><br> traverseKeys :: (IO [String] -> IO [String]) -> DbP -> IO [String]<br> traverseKeys valve db = traverse firstKey<br> where traverse :: (DbP -> IO (Maybe String)) -> IO [String]
<br> traverse func = do nxt <- func db<br> case nxt of<br> Nothing -> return []<br> Just v -> do rest <- valve $
<br> traverse (\db -><br>nextKey db v)<br> return $ v : rest<br><br>Intuition suggests there's a higher-order way of writing 'traverse'.
</blockquote><div><br>'traverse' is a sort of unfold. Here's the type of unfoldr:<br><br>unfoldr :: (b -> Maybe (a,b)) -> b -> [a]<br><br>It's not too hard to implement a monadic version, although I don't think it's in the libraries:
<br><br>unfoldrM :: (Monad m) => (b -> m (Maybe (a,b))) -> b -> m [a]<br>unfoldrM f b = do<br> next <- f b<br> case next of<br> Just (a, b') -> liftM (a:) (unfoldrM f b')<br> Nothing -> return []
<br><br>You can probably see the similarity to traverse. However, the type is different enough from traverse that I don't think it would be that simple to implement traverseKeys in terms of unfoldrM. The fact that traverseKeys uses different functions for the first step and all the rest makes things difficult, too. In the end it looks to me like you're probably better off just implementing traverse directly as you have done, although perhaps someone will find a better way.
<br><br>I will note, however, that the last few lines of traverse can be written more simply as:<br><br>Just v -> liftM (v:) . valve . traverse $ (\db -> nextKey db v)<br><br>or even<br><br>Just v -> liftM (v:) . valve . traverse . flip nextKey $ v
<br><br>Perhaps that's going too far for your taste, but the main point is the liftM (v:); instead of extracting 'rest', consing v, and then putting the new list back in IO with 'return', you can just use liftM to apply the cons function inside the monad in the first place.
<br><br>-Brent</div></div>