On Sun, Dec 13, 2009 at 3:47 AM, Heinrich Apfelmus <apfelmus@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