> import Control.Monad.Tardis | |
> :{ | |
let levels hs = evalTardis (traverse | |
(\h -> do x <- min <$> getFuture <*> getPast -- Get the height of the enclosing walls | |
modifyBackwards (`max` h) -- Send the right max back to the past | |
modifyForwards (`max` h) -- Send the left max into the future | |
pure (max 0 (x - h)) -- Calculate the height of the water itself | |
) hs) (0, 0) | |
:} | |
> sum $ levels [5,3,7,2,6,4,5,9,1,2] | |
14 |
This comment has been minimized.
This comment has been minimized.
@lalaithion Oh, you're right, well spotted! I think we could fix it perhaps by swapping those two lines? |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
This code has a slight subtlety in it that I wouldn't call a bug, strictly speaking, but is perhaps inhibitory to understanding the exact semantics of the Tardis Monad.
If we have a situation where the max height in the Future direction is less than the current height, then the
modifyBackwards
causes thegetFuture
on the previous line to returnh
, not the actual max height in the future direction. In that case, we know thatx
is eitherh
, because there is a bigger number in the Past, orx
is less thanh
, because the Past was a smaller number. Therefore,x - h <= 0
, and we end up with the right answer in the end.However, it's not quite what the code should be doing.