Haskell: Non-strict boolean operations

Question

Is there anyway to define a function like the following in Haskell?

or True      True      = True
or True      undefined = True
or True      False     = True
or undefined True      = True
or undefined False     = undefined
or undefined undefined = undefined
or False     True      = True
or False     undefined = undefined
or False     False     = False

I don't currently have a use case for it (though I'd be interested in one), I'm just interested if it's possible.

Answer 1

This is not possible in standard Haskell, but can be done with an unsafe trick, implemented in the lub library by Conal Elliott.

Basically, you write two functions:

orL True _ = True
orL False x = x

orR = flip orL

and then you can define or a b to be the lub (the least upper bound with respect to "definedness" order) of orL a b and orR a b.

Operationally, it runs both computations in parallel and chooses the first one that succeeds, killing the other.

Even though that works as you proposed, it has important disadvantages. First of all, lub is only safe if its arguments agree (equal unless bottom). If you take lub True False, the result will be non-deterministic, thus violating purity! Second, the performance overhead of running both computations in parallel can become dominating in some conditions (try computing a foldr or False of a large list, for example!).

Answer 2

Depending on your evaluation order (the order in which you inspect values) you can write a lazy version:

Prelude> True || undefined
True
Prelude> undefined || True
*** Exception: Prelude.undefined

Prelude> :t or
or :: [Bool] -> Bool

Prelude> or [True, undefined]
True

in fact, the default definition in Haskell will behave like this, since Haskell is a lazy language.

However, there's no way to "skip" an undefined value, without looking at the value first, which will evaluate it to a bottom, which causes your expression to be undefined.

Remember that lazy values are presents with ghosts inside them:

If you look inside the box, a ghost might get you.

If checking for bottoms is important (e.g. as part of a testsuite) you can treat them as exceptions, and intercept them. But you wouldn't do that in a pure function.