Skip to content

Instantly share code, notes, and snippets.

@paf31 paf31/water.hs Secret
Last active Oct 28, 2019

Embed
What would you like to do?
> 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

This comment has been minimized.

Copy link

lalaithion commented Oct 28, 2019

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 the getFuture on the previous line to return h, not the actual max height in the future direction. In that case, we know that x is either h, because there is a bigger number in the Past, or x is less than h, 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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.