Get best of the week

How much water has leaked? We solve the problem by a moonwalk on Haskell

An interesting task walks on the network, which was asked at an interview on Twitter.
Imagine that you are looking at walls of various heights in profile. It is raining, somewhere the water remains, somewhere it flows over the edges of the wall due to the difference in height. The challenge is to determine how much water remains between the walls.


To represent the sequence of walls, we can use the list:

type Height = Int

walls :: [Height]
walls = [2,5,1,2,3,4,7,7,6]

To find out the volume of water at the top of each wall, we need to know three things:

  1. Current wall height
  2. The height of the highest left wall
  3. The height of the highest right wall

We find out which wall below is right or left, subtract the height of the current wall from the highest and get the volume of water. Let's take a closer look at an example:



Imagine that we need to calculate the volume of water for wall b. The height of the highest left wall - a , is 3 . The height of the highest right wall - s , is 2 . Due to the higher left wall, water will spill out to the right, so we count from the height of the right wall. Therefore, the volume of water for the wall b is = height c - height b = 2 - 1 = 1 .

To solve this problem in one pass of the list will not work, but it will turn out in two - the whole thing is to calculate the upper left and right walls. ( UPD :roman_kashitsynshowed how it is possible for one, only without obtaining information on the volume of accumulated water on each wall)

We begin by calculating the highest left wall for each wall using the state effect:

type Volume = Int

--|        
themax :: Height -> State Height Height
themax h = modify (max h) *> get

-- |            
highest_left :: [Height] -> [Height]
highest_left walls = evalState (traverse themax walls) 0



Now we need to calculate the highest right wall for each of the walls, but in this case we need to start the count not on the left, but on the right. How to be in this case? Turn over the list? As you might have guessed from the title of this article, there is a more interesting method.

Inverse Applicative Functors


An interesting type lives in the transformers package (in the literal and figurative sense of the word). It allows you to run applicative effects in the reverse order:

newtype Backwards f a = Backwards { forwards :: f a }

How it works? Let's take a closer look at the Applicative class instance for Backwards :

-- |          liftA2  <**>
instance Applicative t => Applicative (Backwards t) where
        pure = Backwards . pure
	Backwards f <*> Backwards x = Backwards ((&) <$> x <*> f)

& is the same application of a function to the $ argument , but with a different order of arguments: first the argument, then the function:

f $ x = x & f

Due to laziness, we first compute the second component of the applicative calculation chain, and only then the first - hence the name for this type.

In the same transformers there is another interesting type - Reverse :

newtype Reverse f a = Reverse { getReverse :: f a }

It launches effects in Traversable in reverse using Backwards .

And now back to our original problem with this very type.

We master the moonwalk


“Moonwalk” (from the English moonwalk), or “gliding backward”, is a dance technique when a dancer moves backward, while simulating leg movements as if walking forward. (Wikipedia).
To crank up such a trick, we take the same function with the state effect (as if we were going forward, from left to right), which we used to calculate the highest left wall:

-- |        
themax :: Height -> State Height Height
themax h = modify (max h) *> get

-- |    ,    :
highest_right :: [Height] -> [Height]
highest_right walls = getReverse $ evalState (traverse themax $ Reverse walls)

Now we have everything to calculate the total volume of accumulated water. From the highest left and right walls we select the lowest and subtract the wall height from it - this will be the volume of accumulated water:

walls = [2,5,1,2,3,4,7,7,6]
let hls = highest_left walls = [2,5,5,5,5,5,7,7,7]
let hrs = highest_right walls = [7,7,7,7,7,7,7,7,6]
sum $ zipWith3 (\l x r -> min l r - x) hls walls hrs



So, applicative functors helped us abstract from specific effects and data structures. They have some more interesting uses - grouping queries , sorting .

The source code for this solution can be found here . This puzzle has some more interesting approaches that can be viewed here .

More articles:


All Articles