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

[Heinrich Apfelmus]

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