Jason Dagit wrote:
Heinrich Apfelmus 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.
On second (and late) thought, this idea is not as good as it sounds and needs more thought. The thing is if A is an instance of Small , we are not guaranteed that a value x :: A will take little memory, we are only guaranteed that its *normal form* takes little memory. Now, due to pervasive lazy evaluation, it's quite impossible to track whether a value is in normal form in the type system.
It seems like we also need: instance Small (IO ())
Which is not necessarily bounded due to things like IORefs. [...]
In the light of the above, I think this is related to the issue that we can't evaluate IO () to normal form at all, i.e. there is no deepSeq for values of type IO () .
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.
Thanks to parametricity, we know that b is thrown away, it can never appear in the result type c .
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.
Yep, though this does have the unfortunate (?) consequence that we cannot use bracketSmall to return any large values anymore, even if they do not leak the stream. (A notion which literally gets "muddier" in the course of the program because it might be that c does not leak the vanilla stream, but for example every character of it.) Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com