-
-
Save paf31/9d84ecf6a6a9b69cdb597a390f25764d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
> 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 |
@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 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.