[Haskell-cafe] Laziness and Either

[David Menendez]

On Mon, Apr 21, 2008 at 2:18 PM, John Goerzen <jgoerzen at complete.org> 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?

>From my perspective, the version using Either is lazier. By delaying
any further processing until the input is known to be correct, it
avoids doing unnecessary work.

On the other hand, if space is more of a concern than time, then you
could combine the processing with a left fold that accumulates an
answer.

process :: [Input] -> Either Error [Output]
    -- lazy

processAccum :: (seed -> Input -> seed) -> seed -> [Input] -> Either Error seed
    -- thrifty

The type of 'processAccum' is essentially an encoding of the River
type apfelmus proposed. It's also related to Oleg's left-fold
enumerator pattern[1].

[1] http://okmij.org/ftp/Computation/Continuations.html#enumerator-stream

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>