<br><div><span class="gmail_quote">On 10/26/07, <b class="gmail_sendername">Graham Fawcett</b> &lt;<a href="mailto:graham.fawcett@gmail.com">graham.fawcett@gmail.com</a>&gt; 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 &lt;<a href="mailto:derek.a.elkins@gmail.com">derek.a.elkins@gmail.com</a>&gt; wrote:<br>&gt; On Thu, 2007-10-25 at 11:30 -0400, Graham Fawcett wrote:<br>&gt; &gt; I&#39;m writing a Gnu DBM module as an exercise for learning Haskell and
<br>&gt; &gt; its FFI. I&#39;m wondering how I might write a function that returns the<br>&gt; &gt; database keys as a lazy list.<br>&gt; Just use unsafeInterleaveIO in the obvious definition to read all the<br>&gt; keys.&nbsp;&nbsp;That said, it&#39;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>&nbsp;&nbsp;firstKey :: DbP -&gt; IO (Maybe String)
<br>&nbsp;&nbsp;nextKey :: DbP -&gt; String -&gt; IO (Maybe String)<br><br>I wrote these eager and lazy key-iterators:<br><br>&nbsp;&nbsp;allKeys :: DbP -&gt; IO [String]<br>&nbsp;&nbsp;allKeys = traverseKeys id<br><br>&nbsp;&nbsp;unsafeLazyKeys :: DbP -&gt; IO [String]
<br>&nbsp;&nbsp;unsafeLazyKeys = traverseKeys unsafeInterleaveIO<br><br>&nbsp;&nbsp;traverseKeys :: (IO [String] -&gt; IO [String]) -&gt; DbP -&gt; IO [String]<br>&nbsp;&nbsp;traverseKeys valve db = traverse firstKey<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;where traverse :: (DbP -&gt; IO (Maybe String)) -&gt; IO [String]
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;traverse func = do nxt &lt;- func db<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; case nxt of<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Nothing -&gt; return []<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Just v -&gt; do rest &lt;- valve $
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;traverse (\db -&gt;<br>nextKey db v)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return $ v : rest<br><br>Intuition suggests there&#39;s a higher-order way of writing &#39;traverse&#39;.
</blockquote><div><br>&#39;traverse&#39; is a sort of unfold.&nbsp; Here&#39;s the type of unfoldr:<br><br>unfoldr :: (b -&gt; Maybe (a,b)) -&gt; b -&gt; [a]<br><br>It&#39;s not too hard to implement a monadic version, although I don&#39;t think it&#39;s in the libraries:
<br><br>unfoldrM :: (Monad m) =&gt; (b -&gt; m (Maybe (a,b))) -&gt; b -&gt; m [a]<br>unfoldrM f b = do<br>&nbsp;&nbsp;&nbsp; next &lt;- f b<br>&nbsp;&nbsp;&nbsp; case next of<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Just (a, b&#39;) -&gt; liftM (a:) (unfoldrM f b&#39;)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Nothing -&gt; return []
<br><br>You can probably see the similarity to traverse.&nbsp; However, the type is different enough from traverse that I don&#39;t think it would be that simple to implement traverseKeys in terms of unfoldrM.&nbsp; The fact that traverseKeys uses different functions for the first step and all the rest makes things difficult, too.&nbsp; In the end it looks to me like you&#39;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 -&gt; liftM (v:) . valve . traverse $ (\db -&gt; nextKey db v)<br><br>or even<br><br>Just v -&gt; liftM (v:) . valve . traverse . flip nextKey $ v
<br><br>Perhaps that&#39;s going too far for your taste, but the main point is the liftM (v:); instead of extracting &#39;rest&#39;, consing v, and then putting the new list back in IO with &#39;return&#39;, you can just use liftM to apply the cons function inside the monad in the first place.
<br><br>-Brent</div></div>