[Haskell-cafe] Re: [darcs-users] Iteratees, streams, and mmap

[Jason Dagit]

On Sun, Dec 13, 2009 at 3:47 AM, Heinrich Apfelmus <
apfelmus at quantentunnel.de> wrote:

> How about tracking the requirement of "bounded" in the type system? In
> particular, I'm thinking of a type class
>
>    class NFData a => Small a
>
> where the idea is that all types that can be stored in constant space
> are members of this class. For example, we have
>
>    instance Small ()
>    instance Small Int
>    instance Small Char
>    instance (Small a, Small b) => Small (a,b)
>    instance (Small a, Small b) => Small (Either a b)
>
> but recursive types like  [a]  or  String  are not allowed to be members.
>

I like this.  It's easy to audit for weird instances of Small.

It seems like we also need:
instance Small (IO ())

Which is not necessarily bounded due to things like IORefs.  See below for
why I think it would be a useful instance.


> Then,
>
>    withPending :: Small a => (a -> Patch -> a) -> IO a
>
> which is based on the function
>
>    foldlSmall :: Small b => (b -> a -> b) -> b -> [a] -> b
>    foldlSmall f b []     =
>    foldlSmall f b (x:xs) = foldlSmall f b' xs
>        where b' = rnf (f b x)
>
> is pretty much guaranteed to run in O(1) space. Well, that depends on  f
> , but the point is it's not  foldlSmall  who introduces the space leak,
> it's the argument that takes all the blame.
>

I could also see, us needing this:

bracketSmall :: (Small c) => IO a -> (a -> IO b) -> (a -> IO c) -> IO c

I'm not sure if b needs to be Small, since it's just supposed to be the
return value of the deallocation step.

Actually, since we didn't (yet) make functions an instance of Small, we may
need to say this type:

bracketFoldSmall :: (Small c) => IO a -> (a -> IO b) -> ((c -> a -> c) -> c
-> a -> c) -> IO c

Here I'm imagining 'a', being something like a list of patches.  It's a big
stream we want to process.  Furthermore, it seems like we probably want c =
IO ().  This would be useful if we wanted to do some output for each patch
in the sequence.  But, as I think about it, it seems like if we allow ST or
IO in these "small" functions or as instances of Small then we lose our
guarantees.  Yet, it seems that having functions like bracketSmall are
necessary if we want to hide the stream itself from being exposed outside of
the traversal function.  For example, your foldlSmall doesn't leak, but
something at the same level of scope as it could leak the list.

Jason
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20091213/09275dc1/attachment.html