<br><br><div class="gmail_quote">On Sun, Dec 13, 2009 at 3:47 AM, Heinrich Apfelmus <span dir="ltr"><<a href="mailto:apfelmus@quantentunnel.de">apfelmus@quantentunnel.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
How about tracking the requirement of "bounded" in the type system? In<br>
particular, I'm thinking of a type class<br>
<br>
class NFData a => Small a<br>
<br>
where the idea is that all types that can be stored in constant space<br>
are members of this class. For example, we have<br>
<br>
instance Small ()<br>
instance Small Int<br>
instance Small Char<br>
instance (Small a, Small b) => Small (a,b)<br>
instance (Small a, Small b) => Small (Either a b)<br>
<br>
but recursive types like [a] or String are not allowed to be members.<br></blockquote><div><br>I like this. It's easy to audit for weird instances of Small.<br><br>It seems like we also need:<br>instance Small (IO ())<br>
<br>Which is not necessarily bounded due to things like IORefs. See below for why I think it would be a useful instance.<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>
Then,<br>
<br>
withPending :: Small a => (a -> Patch -> a) -> IO a<br>
<br>
which is based on the function<br>
<br>
foldlSmall :: Small b => (b -> a -> b) -> b -> [a] -> b<br>
foldlSmall f b [] =<br>
foldlSmall f b (x:xs) = foldlSmall f b' xs<br>
where b' = rnf (f b x)<br>
<br>
is pretty much guaranteed to run in O(1) space. Well, that depends on f<br>
, but the point is it's not foldlSmall who introduces the space leak,<br>
it's the argument that takes all the blame.<br></blockquote><div><br>I could also see, us needing this:<br><br>bracketSmall :: (Small c) => IO a -> (a -> IO b) -> (a -> IO c) -> IO c<br><br>I'm not sure if b needs to be Small, since it's just supposed to be the return value of the deallocation step.<br>
<br>Actually, since we didn't (yet) make functions an instance of Small, we may need to say this type:<br><br>bracketFoldSmall :: (Small c) => IO a -> (a -> IO b) -> ((c -> a -> c) -> c -> a -> c) -> IO c<br>
<br>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.<br>
<br>Jason<br></div></div>