[Haskell-cafe] Laziness and Either

[Derek Elkins]

On Mon, 2008-04-21 at 21:26 +0100, Magnus Therning wrote:
> 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

Indeed, years ago this is exactly what I suggested as a possible
solution.  See
http://web.archive.org/web/20061011010615/http://www.haskell.org/hawiki/TyingTheKnot near the bottom.