[darcs-users] Iteratees, streams, and mmap

Heinrich Apfelmus apfelmus at quantentunnel.de
Sat Dec 12 10:42:03 UTC 2009

Jason Dagit wrote:
> My next experiment will be to find ways to express "take this operation and
> apply it to a stream without letting the stream leak". One implication is
> that gzReadFilePS should not be used outside of a core set of modules which
> have been auideted to be resource concious.  Another implication is that we
> need to be really careful about wether or not we allow returning of
> sequences of patches.  Possibly, we need several foldl-like functions that
> open the stream internally.  For example, to process the pending maybe we
> should have:
> withPending :: (a -> Patch -> a) ->  IO a
> And withPending would start the streaming and make sure that the stream
> cannot be visible as a data dependency outside of withPending.

Just a small comment on a potential flaw in this scheme and the
observation that even the rank-2 type trick from the  ST s  monad
wouldn't help.

Namely,  withPending  does not guarantee that the stream does not leak,
it only makes it more natural/convenient to formulate one's code so that
it doesn't leak. In particular, using  (:)  as argument pretty much
defeats the whole purpose:

   withPending (flip (:))

Fortunately, the type system can ensure that the patches don't leak.

   withPending :: (forall s. a -> Patch s -> a) -> IO a

Now,  a  may not mention  s  and the type checker will reject  flip (:)
 as argument. See also

  Oleg Kiselyov, Chung-chieh Shan.
  Lightweight Monadic Regions.

for an elaboration of this technique.

However, the line between leaking and not leaking is very thin here. As
soon as we are given for example a function

   name :: Patch s -> String

that discards the  s , its results can "leak", in the sense that we
could now build a list of names

   foo :: IO [String]
   foo = withPending . flip $ (:) . name

Even worse, any type  a  that doesn't have O(1) space usage will "leak"

   bar :: IO [()]
   bar = withPending . flip $ const (() :)

In other words, exporting only a  foldl' -like interface does not really
prevent us from writing functions that have O(n) instead of O(1) space
usage. But trying to rectify that with the  forall s  trick is a doomed
idea, too.

Heinrich Apfelmus


More information about the darcs-users mailing list