[Haskell-cafe] Laziness and Either

[Magnus Therning]

John Goerzen wrote:
> Back when I was working on the logic for the bin-packing solver that I added 
> to MissingH (for use with datapacker), I had a design decision to make: do I 
> raise runtime errors with the input using error, or do I use an Either type 
> to return errors?
> 
> Initially, for simplicity, I just used error.  But when I did a simple 
> refactoring to use Either, it occurred to me that this switch likely had a 
> negative impact on laziness.
> 
> In this particular algorithm, we cannot tell for sure that we have no errors 
> until we have consumed all items of the input list.  This is unlike, say, a 
> safe version of "head" where you can tell whether you have an error just by 
> whether you have an empty list or not.
> 
> In the case of using "error", we can happily process the data assuming 
> everything will be fine, and raise an error if and when it is encountered.  
> By using Either, however, any pattern match on the Left/Right result is 
> going to force the entire input to be evaluated so that we can know whether 
> or not it had any error.
> 
> Is this analysis sensible?  If so, are there better solutions?

This reminds me of a problem I had in dataenc[1], when trying to decode
large files I ran out of memory.  It was simple to track that down to my
decision to use Maybe for the return type.  Originally I only had one
function for decoding:

  decode :: String -> Maybe [Word8]
  decode = sequence . decode'

In order to allow lazy decoding I ended up exporting decode' as well:

  decode' :: String -> [Maybe Word8]

Unfortunately that pushes handling of decoding errors to the layer
above.  Not ideal maybe, but it was the easiest solution.

Duncan mentioned that iconv took a similar route to provide laziness[2].

I'm curious to see whether Malcom's paper can offer some further insight.

/M

[1]: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dataenc
[2]: http://www.haskell.org/pipermail/haskell-cafe/2007-December/036282.html

-- 
Magnus Therning                             (OpenPGP: 0xAB4DFBA4)
magnus＠therning．org             Jabber: magnus．therning＠gmail．com
http://therning.org/magnus

What if I don't want to obey the laws? Do they throw me in jail with
the other bad monads?
     -- Daveman

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: OpenPGP digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080421/f8059966/signature.bin