Get best of the week

¿Cuánta agua se ha filtrado? Resolvemos el problema con un paseo lunar en Haskell

Una tarea interesante recorre la red, que se hizo en una entrevista en Twitter.
Imagine que está mirando paredes de diferentes alturas de perfil. Está lloviendo, en algún lugar permanece el agua, en algún lugar fluye sobre los bordes de la pared debido a la diferencia de altura. El desafío es determinar cuánta agua queda entre las paredes.


Para representar la secuencia de paredes, podemos usar la lista:

type Height = Int

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

Para averiguar el volumen de agua en la parte superior de cada pared, necesitamos saber tres cosas:

  1. Altura actual de la pared
  2. La altura del muro izquierdo más alto
  3. La altura del muro más alto de la derecha

Averiguamos qué pared debajo es derecha o izquierda, restamos la altura de la pared actual de la más alta y obtenemos el volumen de agua. Echemos un vistazo más de cerca a un ejemplo:



imagine que necesitamos calcular el volumen de agua para la pared b. La altura de la pared izquierda más alta - a , es 3 . La altura de la pared derecha más alta - s , es 2 . Debido a la pared superior izquierda, el agua se derramará hacia la derecha, por lo que contamos desde la altura de la pared derecha. Por lo tanto, el volumen de agua para la pared b es = altura c - altura b = 2 - 1 = 1 .

Resolver este problema en una pasada de la lista no funcionará, pero resultará en dos: todo es calcular las paredes superior izquierda y derecha. ( UPD :roman_kashitsynmostramos cómo es posible para uno, solo sin obtener información sobre el volumen de agua acumulada en cada pared)

Comenzamos calculando la pared izquierda más alta para cada pared usando el efecto de estado:

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



Ahora necesitamos calcular la pared más alta de la derecha para cada una de las paredes, pero en este caso necesitamos comenzar el conteo no a la izquierda, sino a la derecha. ¿Cómo estar en este caso? ¿Voltear la lista? Como habrás adivinado por el título de este artículo, hay un método más interesante.

Functores aplicativos inversos


Un tipo interesante vive en el paquete de transformadores (en el sentido literal y figurado de la palabra). Le permite ejecutar efectos aplicativos en el orden inverso:

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

¿Cómo funciona? Echemos un vistazo más de cerca a la instancia de clase Aplicativa para Atrás :

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

& es la misma aplicación de una función al argumento $ , pero con un orden diferente de argumentos: primero el argumento, luego la función:

f $ x = x & f

Debido a la pereza, primero calculamos el segundo componente de la cadena de cálculos aplicativos, y solo luego el primero, de ahí el nombre de este tipo.

En los mismos transformadores hay otro tipo interesante: inversa :

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

Lanza efectos en Traversable en reversa usando Al revés .

Y ahora volvamos a nuestro problema original con este mismo tipo.

Dominamos el moonwalk


"Moonwalk" (del inglés moonwalk), o "deslizarse hacia atrás", es una técnica de baile cuando un bailarín se mueve hacia atrás, mientras simula el movimiento de sus piernas como si caminara hacia adelante. (Wikipedia)
Para poner en marcha tal truco, tomamos la misma función con el efecto de estado (como si avanzáramos, de izquierda a derecha), que usamos para calcular la pared izquierda más alta:

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

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

Ahora tenemos todo para calcular el volumen total de agua acumulada. De las paredes superiores izquierda y derecha seleccionamos la más baja y le restamos la altura de la pared; este será el volumen de agua acumulada:

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



Entonces, los functores aplicativos nos ayudaron a abstraer de efectos específicos y estructuras de datos. Tienen algunos usos más interesantes: consultas de agrupación , clasificación .

El código fuente de esta solución se puede encontrar aquí . Este rompecabezas tiene algunos enfoques más interesantes que se pueden ver aquí .

More articles:


All Articles