[Haskell-cafe] Laziness and Either
derek.a.elkins at gmail.com
Tue Apr 22 23:52:35 EDT 2008
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, 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.
> I'm curious to see whether Malcom's paper can offer some further insight.
> : http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dataenc
> : http://www.haskell.org/pipermail/haskell-cafe/2007-December/036282.html
Indeed, years ago this is exactly what I suggested as a possible
http://web.archive.org/web/20061011010615/http://www.haskell.org/hawiki/TyingTheKnot near the bottom.
More information about the Haskell-Cafe