[Haskell-cafe] Laziness and Either
magnus at therning.org
Mon Apr 21 16:26:04 EDT 2008
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.
Magnus Therning (OpenPGP: 0xAB4DFBA4)
magnus＠therning．org Jabber: magnus．therning＠gmail．com
What if I don't want to obey the laws? Do they throw me in jail with
the other bad monads?
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 189 bytes
Desc: OpenPGP digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080421/f8059966/signature.bin
More information about the Haskell-Cafe