'lazy mindset' was: HUGS error: Unresolved overloading

Marcin 'Qrczak' Kowalczyk qrczak@knm.org.pl
22 May 2001 20:53:57 GMT


I have a case where I don't know how to apply laziness well.

Consider mutable containers (e.g. STArray or a database on disk).
How to iterate over them? I see the following possibilities:

* Give up laziness, provide only a conversion to the list of items.
  Since the conversion is monadic, it must construct the whole
  list before it returns. Such conversion must be present anyway,
  especially as this is the only way to ensure that we snapshot
  consistent contents, and it can be argued that we usually don't
  really need that much anything more sophisticated, and for some
  cases we might get values by keys/indices generated in some lazy way.

* Use unsafeInterleaveIO and do a similar thing to hGetContents.
  Easy to use but impure and dangerous if evaluation is not forced
  early enough.

* Invent a lazy monadic sequence:
      newtype Lazy m a = Lazy {getBegin :: m (Maybe (a, Lazy m a))}
  (This can't be just
      type Lazy m a = m (Maybe (a, Lazy m a))
  because it would be a recursive type.)
  
  It's generic: I can iterate over a collection and stop at any point.
  But using it is not a pleasure. Some generic operations make sense
  for this without changing the interface (filter, takeWhile), some
  don't (filterM - it can't work for arbitrary monad, only for the
  one used in the particular lazy sequence), and it's needed to have
  separate versions of some operations, e.g.
      filterLazy :: Monad m => (a -> m Bool) -> Lazy m a -> Lazy m a
  which fits neither filter nor filterM. It artificially splits my
  class design or requires methods implemented as error "sorry, not
  applicable".

* Introduce a stateful iterator, like C++ or Java. This is ugly but
  would work too. Probably just the simplest version, i.e.
      getIter :: SomeMutableContainer m a -> m (m (Maybe a))
  without going backwards etc.

Suggestions? I think I will do the last choice, after realizing that
Lazy m a is not that nice, but perhaps it can be done better...

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK