Lazy Evaluation when multiplied by zero
In the below program
f 0 0 0 1 = 0
f 0 0 1 0 = f 0 0 0 1 + 1
f 0 1 0 0 = f 0 0 1 1 + 1
f 1 0 0 0 = f 0 1 1 1 + 1
f a b c d = (p + q + r + s) / (a + b + c + d)
where
p
| a > 0 = a * f (a - 1) (b + 1) (c + 1) (d + 1)
| otherwise = 0
q
| b > 0 = b * f a (b - 1) (c + 1) (d + 1)
| otherwise = 0
r
| c > 0 = c * f a b (c - 1) (d + 1)
| otherwise = 0
s
| d > 0 = d * f a b c (d - 1)
| otherwise = 0
main = print (f 1 1 1 1)
I thought it could be simplified as
f 0 0 0 1 = 0
f 0 0 1 0 = f 0 0 0 1 + 1
f 0 1 0 0 = f 0 0 1 1 + 1
f 1 0 0 0 = f 0 1 1 1 + 1
f a b c d = (p + q + r + s) / (a + b + c + d)
where
p = a * f (a - 1) (b + 1) (c + 1) (d + 1)
q = b * f a (b - 1) (c + 1) (d + 1)
r = c * f a b (c - 1) (d + 1)
s = d * f a b c (d - 1)
main = print (f 1 1 1 1)
because besides the fact that both are mathematically sound, I thought that with lazy evaluation, the compiler or interpreter should be able to decide that multiplying something by 0 is useless. But okay, the program did go into an infinite loop. Why is that?
source to share
Built-in multiplication is strict on both arguments, that is, it evaluates both arguments - regardless of whether one of them is equal to zero, which causes your program to loop. You can define your own multiplication operator that lazily excludes one argument or the other:
0 .* y = 0
x .* y = x * y
or vice versa. It takes a little more to define an operator that eliminates null on both sides, but this can be done with a package unamb
:
x .* y = unambs [ assuming (x == 0) 0
, assuming (y == 0) 0
, x * y
]
Although, as far as I know, this does not yet have a robust enough implementation: - /.
source to share
Apart from defining your own multiplication operator, as @luqui suggests, you can define your own type, whose built-in short circuits are:
newtype SCZero a = SCZero a
deriving Eq
instance Show a => Show (SCZero a) where
show (SCZero x) = show x
instance (Eq a, Num a) => Num (SCZero a) where
SCZero x + SCZero y = SCZero (x + y)
SCZero 0 * SCZero y = SCZero 0
SCZero x * SCZero y = SCZero (x * y)
abs (SCZero x) = SCZero (abs x)
signum (SCZero x) = SCZero (signum x)
fromInteger x = SCZero (fromInteger x)
negate (SCZero x) = SCZero (negate x)
instance (Eq a, Fractional a) => Fractional (SCZero a) where
fromRational x = SCZero (fromRational x)
SCZero 0 / SCZero y = SCZero 0
SCZero x / SCZero y = SCZero (x / y)
Then you can use your existing code directly by simply specifying the result type as SCZero
:
*Main> print (f 1 1 1 1 :: SCZero Double)
0.464398781601087
source to share