suma pattern numeros complejos haskell coding-style functional-programming

pattern - ¿Hay una manera de representar elegantemente este patrón en Haskell?



pattern matching haskell (6)

Tenga en cuenta la función pura a continuación, en un lenguaje imperativo:

def foo(x,y): x = f(x) if a(x) if c(x): x = g(x) else: x = h(x) x = f(x) y = f(y) if a(y) x = g(x) if b(y) return [x,y]

Esa función representa un estilo en el que tienes que actualizar incrementalmente las variables. Se puede evitar en la mayoría de los casos, pero hay situaciones en las que ese patrón es inevitable, por ejemplo, escribir un procedimiento de cocción para un robot, que requiere una serie de pasos y decisiones. Ahora, imagina que estábamos tratando de representar a foo en Haskell.

foo x0 y0 = let x1 = if a x0 then f x0 else x0 in let x2 = if c x1 then g x1 else h x1 in let x3 = f x2 in let y1 = if a y0 then f y0 else y0 in let x4 = if b y1 then g x3 else x3 in [x4,y1]

Ese código funciona, pero es demasiado complicado y propenso a errores debido a la necesidad de administrar manualmente las etiquetas numéricas. Observe que, después de que se establece x1 , el valor de x0 nunca se debe usar de nuevo, pero aún puede. Si lo usas accidentalmente, será un error no detectado.

He logrado resolver este problema usando la mónada estatal:

fooSt x y = execState (do (x,y) <- get when (a x) (put (f x, y)) (x,y) <- get if c x then put (g x, y) else put (h x, y) (x,y) <- get put (f x, y) (x,y) <- get when (a y) (put (x, f y)) (x,y) <- get when (b y) (put (g x, x))) (x,y)

De esta manera, la necesidad de seguimiento de etiquetas desaparece, así como el riesgo de usar accidentalmente una variable obsoleta. Pero ahora el código es detallado y mucho más difícil de entender, principalmente debido a la repetición de (x,y) <- get .

Entonces, ¿ cuál es una forma más legible, elegante y segura de expresar este patrón ?

Código completo para la prueba.

Tus metas

Mientras que la transformación directa del código imperativo generalmente llevaría a la mónada ST y STRef , pensemos en lo que realmente quieres hacer:

  1. Quieres manipular los valores condicionalmente.
  2. Quieres devolver ese valor.
  3. Quieres secuenciar los pasos de tu manipulación.

Requerimientos

Ahora bien, esto se parece primero a la mónada ST . Sin embargo, si seguimos las simples leyes de la mónada, junto con la notación do , vemos que

do x <- return $ if somePredicate x then g x else h x x <- return $ if someOtherPredicate x then a x else b x

Es exactamente lo que quieres. Como solo necesita las funciones más básicas de una mónada ( return y >>= ), puede usar la más sencilla:

La mónada de la Identity

foo x y = runIdentity $ do x <- return $ if a x then f x else x x <- return $ if c x then g x else h x x <- return $ f x y <- return $ if a x then f y else y x <- return $ if b y then g x else y return (x,y)

Tenga en cuenta que no puede usar let x = if ax then fx else x , porque en este caso x sería la misma en ambos lados, mientras que

x <- return $ if a x then f x else x

es lo mismo que

(return $ if a x then (f x) else x) >>= /x -> ...

y la x en la expresión if claramente no es la misma que la resultante, que se utilizará en la lambda en el lado derecho.

Ayudantes

Para que esto quede más claro, puede agregar ayudantes como

condM :: Monad m => Bool -> a -> a -> m a condM p a b = return $ if p then a else b

Para obtener una versión aún más concisa:

foo x y = runIdentity $ do x <- condM (a x) (f x) x x <- fmap f $ condM (c x) (g x) (h x) y <- condM (a y) (f y) y x <- condM (b y) (g x) x return (x , y)

Locura ternaria

Y mientras estamos en condiciones de hacerlo, podemos aumentar la locura e introducir un operador ternario:

(?) :: Bool -> (a, a) -> a b ? ie = if b then fst ie else snd ie (??) :: Monad m => Bool -> (a, a) -> m a (??) p = return . (?) p (#) :: a -> a -> (a, a) (#) = (,) infixr 2 ?? infixr 2 # infixr 2 ? foo x y = runIdentity $ do x <- a x ?? f x # x x <- fmap f $ c x ?? g x # h x y <- a y ?? f y # y x <- b y ?? g x # x return (x , y)

Pero la conclusión es que la mónada de Identity tiene todo lo que necesita para esta tarea.

Imperativo o no imperativo

Uno podría discutir si este estilo es imperativo. Definitivamente es una secuencia de acciones. Pero no hay estado, a menos que cuentes las variables enlazadas. Sin embargo, un paquete de declaraciones let … in … también da una secuencia implícita: espera que la primera let vincule primero.

Usar la Identity es puramente funcional

De cualquier manera, el código anterior no introduce mutabilidad. x no se modifica, en vez de eso, tienes una nueva x o y sigue la última. Esto se aclara si desaparece la expresión do como se indicó anteriormente:

foo x y = runIdentity $ a x ?? f x # x >>= /x -> c x ?? g x # h x >>= /x -> return (f x) >>= /x -> a y ?? f y # y >>= /y -> b y ?? g x # x >>= /x -> return (x , y)

Deshacerse de la mónada más sencilla.

Sin embargo, si usáramos (?) En el lado izquierdo y elimináramos el return s, podríamos reemplazar (>>=) :: ma -> (a -> mb) -> mb) por algo con tipo a -> (a -> b) -> b . Esto solo pasa a ser flip ($) . Terminamos con:

($>) :: a -> (a -> b) -> b ($>) = flip ($) infixr 0 $> -- same infix as ($) foo x y = a x ? f x # x $> /x -> c x ? g x # h x $> /x -> f x $> /x -> a y ? f y # y $> /y -> b y ? g x # x $> /x -> (x, y)

Esto es muy similar a la expresión de desugared anterior. Tenga en cuenta que cualquier uso de Identity se puede transformar en este estilo, y viceversa.

@Sibi lo dijo mejor en su comentario:

Le sugiero que deje de pensar de forma imperativa y que piense de una manera funcional. Estoy de acuerdo en que tomará algún tiempo acostumbrarse al nuevo patrón, pero tratar de traducir ideas imperativas a lenguajes funcionales no es un gran enfoque.

En términos prácticos, su cadena de let puede ser un buen punto de partida:

foo x0 y0 = let x1 = if a x0 then f x0 else x0 in let x2 = if c x1 then g x1 else h x1 in let x3 = f x2 in let y1 = if a y0 then f y0 else y0 in let x4 = if b y1 then g x3 else x3 in [x4,y1]

Pero sugeriría usar una sola let y dar nombres descriptivos a las etapas intermedias.

Desafortunadamente, en este ejemplo no tengo ni idea de lo que hacen las distintas x y y, por lo tanto, no puedo sugerir nombres significativos. En el código real, usaría nombres como x_normalized , x_translated o similares, en lugar de x1 y x2 , para describir cuáles son realmente esos valores.

De hecho, en un let o where que realmente no hay variables: son solo nombres abreviados que se le dan a los resultados intermedios, para facilitar la composición de la expresión final (la que está después in o antes de where ).

Este es el espíritu detrás de x_bar y x_baz continuación. Trate de encontrar nombres que sean razonablemente descriptivos, dado el contexto de su código.

foo x y = let x_bar = if a x then f x else x x_baz = f if c x_bar then g x_bar else h x_bar y_bar = if a y then f y else y x_there = if b y_bar then g x_baz else x_baz in [x_there, y_bar]

Luego, puede comenzar a reconocer patrones que estaban ocultos en el código imperativo. Por ejemplo, x_bar y y_bar son básicamente la misma transformación, aplicada respectivamente a x e y : es por eso que tienen el mismo sufijo "_bar" en este ejemplo sin sentido; entonces es probable que su x2 no necesite un nombre intermedio, ya que simplemente puede aplicar f al resultado completo de "si c y g else h".

Continuando con el reconocimiento de patrones, debe factorizar las transformaciones que está aplicando a las variables en sub-lambdas (o como se llame a las funciones auxiliares definidas en una cláusula where ).

Nuevamente, no tengo ni idea de lo que hizo el código original, por lo que no puedo sugerir nombres significativos para las funciones auxiliares. En una aplicación real, f_if_a se llamaría normalize_if_needed o thaw_if_frozen o mow_if_overgrown ... obtienes la idea:

foo x y = let x_bar = f_if_a x y_bar = f_if_a y x_baz = f (g_if_c_else_h x_bar) x_there = g_if_b x_baz y_bar in [x_there, y_bar] where f_if_a x | a x = f x | otherwise = x g_if_c_else_h x | c x = g x | otherwise = h x g_if_b x y | b y = g x | otherwise = x

No ignore este negocio de nombres.

El punto central de Haskell y otros lenguajes puramente funcionales es expresar algoritmos sin el operador de asignación, es decir , la herramienta que puede modificar el valor de una variable existente.

Los nombres que le dan a las cosas dentro de una definición de función, ya sea que se introduzcan como argumentos, let o where , solo pueden referirse a un valor (o función auxiliar) en toda la definición, para que su código se pueda razonar más fácilmente y se demuestre que es correcto. .

Si no les da nombres significativos (y, por el contrario, le da a su código una estructura significativa), está perdiendo todo el propósito de Haskell.

(En mi humilde opinión, las otras respuestas hasta ahora, citando mónadas y otros chanchullos, están ladrando al árbol equivocado).

El problema que plantea parece una buena aplicación para las arrows :

import Control.Arrow if'' :: (a -> Bool) -> (a -> a) -> (a -> a) -> a -> a if'' p f g x = if p x then f x else g x foo2 :: (Int,Int) -> (Int,Int) foo2 = first (if'' c g h . if'' a f id) >>> first f >>> second (if'' a f id) >>> (/(x,y) -> (if b y then g x else x , y))

en particular, first levanta una función a -> b a (a,c) -> (b,c) , que es más idiomática.

Editar: if'' permite un ascensor

import Control.Applicative (liftA3) -- a functional if for lifting if'''' b x y = if b then x else y if'' :: (a -> Bool) -> (a -> a) -> (a -> a) -> a -> a if'' = liftA3 if''''

Este es un trabajo para la biblioteca ST (transformador de estado).

ST proporciona:

  • Cálculos con estado en la forma del tipo ST . runST ST sa para un cálculo que da como resultado un valor de tipo a , y se puede ejecutar con runST para obtener a valor puro.
  • Referencias mutables de primera clase en forma de tipo STRef . El newSTRef a action crea una nueva referencia de STRef sa con un valor inicial de a , y que puede leerse con readSTRef ref y escribirse con writeSTRef ref a . Un solo cálculo de ST puede usar cualquier número de referencias STRef internamente.

Juntos, estos le permiten expresar la misma funcionalidad de variable mutable como en su ejemplo imperativo.

Para usar ST y STRef, necesitamos importar:

{-# LANGUAGE NoMonomorphismRestriction #-} import Control.Monad.ST.Safe import Data.STRef

En lugar de usar el readSTRef y writeSTRef bajo nivel en todo el lugar, podemos definir los siguientes ayudantes para que coincidan con las operaciones imperativas que utiliza el ejemplo foo estilo Python:

-- STRef assignment. (=:) :: STRef s a -> ST s a -> ST s () ref =: x = writeSTRef ref =<< x -- STRef function application. ($:) :: (a -> b) -> STRef s a -> ST s b f $: ref = f `fmap` readSTRef ref -- Postfix guard syntax. if_ :: Monad m => m () -> m Bool -> m () action `if_` guard = act'' =<< guard where act'' b = if b then action else return ()

Esto nos permite escribir:

  • ref =: x para asignar el valor del cálculo de ST x a la ref STRef.
  • (f $: ref) para aplicar una función pura f a la ref STRef.
  • action `if_` guard para ejecutar la action solo si el resultado es true.

Con estos ayudantes en su lugar, podemos traducir fielmente la definición imperativa original de foo en Haskell:

a = (< 10) b = even c = odd f x = x + 3 g x = x * 2 h x = x - 1 f3 x = x + 2 -- A stateful computation that takes two integer STRefs and result in a final [x,y]. fooST :: Integral n => STRef s n -> STRef s n -> ST s [n] fooST x y = do x =: (f $: x) `if_` (a $: x) x'' <- readSTRef x if c x'' then x =: (g $: x) else x =: (h $: x) x =: (f $: x) y =: (f $: y) `if_` (a $: y) x =: (g $: x) `if_` (b $: y) sequence [readSTRef x, readSTRef y] -- Pure wrapper: simply call fooST with two fresh references, and run it. foo :: Integral n => n -> n -> [n] foo x y = runST $ do x'' <- newSTRef x y'' <- newSTRef y fooST x'' y'' -- This will print "[9,3]". main = print (foo 0 0)

Puntos a tener en cuenta:

  • Aunque primero tuvimos que definir algunos ayudantes sintácticos ( =: $: if_ ) antes de traducir foo , esto demuestra cómo puedes usar ST y STRef como base para desarrollar tu propio lenguaje imperativo que se adapta directamente al problema en cuestión.
  • Sintaxis aparte, esto coincide exactamente con la estructura de la definición imperativa original, sin ninguna reestructuración propensa a errores. Cualquier cambio menor en el ejemplo original se puede reflejar directamente en Haskell. (La adición del enlace temporal x'' <- readSTRef x en el código de Haskell es solo para usarlo con la sintaxis nativa if / else: si se desea, se puede reemplazar con una construcción adecuada basada en ST si / else. )
  • El código anterior demuestra que se dan interfaces puras y con estado al mismo cálculo: los llamadores puros pueden usar foo sin saber que usa un estado mutable internamente, mientras que los llamadores ST pueden usar fooST directamente (y, por ejemplo, pueden proporcionarle STRefs existentes para modificar).

Probablemente haría algo como esto:

foo x y = ( x'', y'' ) where x'' = bgf y'' . cgh . af $ x y'' = af y af z = (if a z then f else id) z cgh z = (if c z then g else h) z bg y x = (if b y then g else id) x

Para algo más complicado, puedes considerar usar lentes:

whenM :: Monad m => m Bool -> m () -> m () whenM c a = c >>= /res -> when res a ifM :: Monad m => m Bool -> m a -> m a -> m a ifM mb ml mr = mb >>= /b -> if b then ml else mr foo :: Int -> Int -> (Int, Int) foo = curry . execState $ do whenM (uses _1 a) $ _1 %= f ifM (uses _1 c) (_1 %= g) (_1 %= h) _1 %= f whenM (uses _2 a) $ _2 %= f whenM (uses _2 b) $ do _1 %= g

Y no hay nada que le impida utilizar nombres de variables más descriptivos:

foo :: Int -> Int -> (Int, Int) foo = curry . execState $ do let x :: Lens (a, c) (b, c) a b x = _1 y :: Lens (c, a) (c, b) a b y = _2 whenM (uses x a) $ x %= f ifM (uses x c) (x %= g) (x %= h) x %= f whenM (uses y a) $ y %= f whenM (uses y b) $ do x %= g

Siempre prefiero los transformadores de estado en capas a usar un solo estado en lugar de una tupla: definitivamente divide las cosas al permitirle "enfocarse" en una capa específica (representaciones de las variables x e y en nuestro caso):

import Control.Monad.Trans.Class import Control.Monad.Trans.State foo :: x -> y -> (x, y) foo x y = (flip runState) y $ (flip execStateT) x $ do get >>= /v -> when (a v) (put (f v)) get >>= /v -> put ((if c v then g else h) v) modify f lift $ get >>= /v -> when (a v) (put (f v)) lift get >>= /v -> when (b v) (modify g)

La función de lift nos permite enfocarnos en la capa de estado interno, que es y .