[Haskell-cafe] lazily traversing a foreign data structure

[Graham Fawcett]

On 10/25/07, Derek Elkins <derek.a.elkins at gmail.com> wrote:
> On Thu, 2007-10-25 at 11:30 -0400, Graham Fawcett wrote:
> > I'm writing a Gnu DBM module as an exercise for learning Haskell and
> > its FFI. I'm wondering how I might write a function that returns the
> > database keys as a lazy list.
> Just use unsafeInterleaveIO in the obvious definition to read all the
> keys.  That said, it's not called unsafeInterleaveIO for no reason.

I got it to work, using unsafeInterleaveIO. Thanks! But I suspect I
might be working too hard to get the result. Is anyone willing to
critique my code?

Given firstKey and nextKey:

  firstKey :: DbP -> IO (Maybe String)
  nextKey :: DbP -> String -> IO (Maybe String)

I wrote these eager and lazy key-iterators:

  allKeys :: DbP -> IO [String]
  allKeys = traverseKeys id

  unsafeLazyKeys :: DbP -> IO [String]
  unsafeLazyKeys = traverseKeys unsafeInterleaveIO

  traverseKeys :: (IO [String] -> IO [String]) -> DbP -> IO [String]
  traverseKeys valve db = traverse firstKey
      where traverse :: (DbP -> IO (Maybe String)) -> IO [String]
            traverse func = do nxt <- func db
                               case nxt of
                                 Nothing -> return []
                                 Just v -> do rest <- valve $
                                                      traverse (\db ->
nextKey db v)
                                              return $ v : rest

Intuition suggests there's a higher-order way of writing 'traverse'.

(It was an 'aha' moment for me to realize Haskell would let me choose
strict or lazy evaluation by passing in a different 'valve'
function. Powerful stuff.)

Thanks again,
Graham