2010-03-17 22 views
17

Tengo este código que quiero hacer sin puntos;Sin puntos en Haskell

(\k t -> chr $ a + flip mod 26 (ord k + ord t -2*a))

¿Cómo puedo hacer eso?

También hay algunas reglas generales para el estilo sin puntos que no sean "pensar en esto y encontrar algo"?

+3

¿Por qué le gustaría dejarlo sin puntos? – yfeldblum

+1

Porque poder escribir código sin puntos parece una de las propiedades de un buen programador Haskell. – Igor

+10

A veces, el código sin puntos es más claro que su alternativa sin puntos, y luego es una buena idea usar estilos sin puntos. Este no es uno de esos momentos. – dave4420

Respuesta

52

Para activar una función

func x y z = (some expression in x, y and z) 

en forma libre puntos, por lo general trato de seguir lo que se hace para el último parámetro z y escribir la función como

func x y z = (some function pipeline built using x and y) z 

entonces puedo cancelar la z s para obtener

func x y = (some function pipeline built using x and y) 

Luego, repetir g el proceso para yyx debe terminar con func en forma libre de puntos.Una transformación esencial reconocer en este proceso es:

f z = foo $ bar z -- or f z = foo (bar z) 
<=> f z = foo . bar $ z 
<=> f = foo . bar 

También es importante recordar que la evaluación parcial, se puede "romper" el último argumento a una función:

foo $ bar x y == foo . bar x $ y -- foo applied to ((bar x) applied to y) 

Para su especial función, tenga en cuenta que el flujo k y t pasan por:

  1. ord Aplicar a cada uno de ellos
  2. Añadir los resultados
  3. Reste 2 * a
  4. tomar el resultado mod 26
  5. Añadir un
  6. Aplicar chr

Así como un primer intento de simplificar, se obtiene:

func k t = chr . (+a) . (`mod` 26) . subtract (2*a) $ ord k + ord t 

Tenga en cuenta que puede evitar flip usando una sección en mod, y las secciones que usan - se desordenan en Haskell por lo que hay una función subtract (chocan con la sintaxis para escribir números negativos: (-2) significa negativo 2, y no es lo mismo que subtract 2).

En esta función, ord k + ord t es un excelente candidato para el uso de Data.Function.on (link). Este combinador de utilidad nos permite reemplazar ord k + ord t con una función aplicada a k y t:

func k t = chr . (+a) . (`mod` 26) . subtract (2*a) $ ((+) `on` ord) k t 

Ahora estamos muy cerca de tener

func k t = (function pipeline) k t 

y por lo tanto

func = (function pipeline) 

Desafortunadamente Haskell es un poco complicado cuando se trata de componer una función binaria con una secuencia de funciones unarias, pero hay un truco (veré si puedo encontrar un buena referencia para ello), y nos encontramos con:

import Data.Function (on) 

func = ((chr . (+a) . (`mod` 26) . subtract (2*a)) .) . ((+) `on` ord) 

que es casi una buena canalización función libre de punto limpio, a excepción de que la composición truco feo. Al definir el operador .: sugerido en los comentarios on this page, esto arregla un poco para:

import Data.Function (on) 

(.:) = (.).(.) 

func = (chr . (+a) . (`mod` 26) . subtract (2*a)) .: ((+) `on` ord) 

Para pulir esto un poco más, se podría añadir algunas funciones de ayuda a separar la letra < - conversión> Int desde el Caesar cipher aritmética . Por ejemplo: letterToInt = subtract a . ord

+3

+1 Eso es realmente muy legible – jberryman

+3

Increíble combinador fu . +1 –

+22

+1 para usar el combinador de tetas – SamB

0

Connect en IRC, #haskell y ask lambdabot !:

<you> @pl (\k t -> chr $ a + flip mod 26 (ord k + ord t -2*a)) 
<lambdabot> [the answer] 
+0

+1 para buenas referencias. -1 por no publicar una respuesta real. – Earlz

+0

No publicado ya porque estoy tratando de resolverlo a mano, en lugar de preguntarle a lambdabot ... Se viene una edición. –

+0

Bah, se me ocurrió dejar f1 = \ a -> (chr.). ((a +).). ((flip mod 26).). (. ord). (+). ((-) (2 * a)). ord - pero da los resultados incorrectos y no tengo ganas de depurarlo ahora :) –

10

También hay algunas reglas generales para el estilo libre de punto que no sea "pensar en esto amd llegar a algo"?

Siempre se puede engañar y utilizar la función "PL" de lambdabot (ya sea yendo a #haskell en freenode o utilizando por ejemplo ghci on acid). Para su código PL da:

((chr . (a +) . flip mod 26) .) . flip flip (2 * a) . ((-) .) . (. ord) . (+) . ord

que no es realmente una mejora si me preguntas.

+7

Por eso "pl" es corto para inútil, no sin puntos :) –

3

Definitivamente hay un conjunto de trucos para transformar una expresión en un estilo sin puntos. No pretendo ser un experto, pero aquí hay algunos consejos.

En primer lugar, desea aislar los argumentos de la función en el término más a la derecha de la expresión.Sus herramientas principales aquí se flip y $, usando las reglas:

f a b ==> flip f b a 
f (g a) ==> f $ g a 

donde fg y son funciones, y a y b son expresiones. Así que para empezar:

(\k t -> chr $ a + flip mod 26 (ord k + ord t -2*a)) 
-- replace parens with ($) 
(\k t -> chr $ (a +) . flip mod 26 $ ord k + ord t - 2*a) 
-- prefix and flip (-) 
(\k t -> chr $ (a +) . flip mod 26 $ flip (-) (2*a) $ ord k + ord t) 
-- prefix (+) 
(\k t -> chr $ (a +) . flip mod 26 $ flip (-) (2*a) $ (+) (ord k) (ord t)) 

Ahora tenemos que conseguir t a cabo en el lado derecho. Para ello, utilice la regla:

f (g a) ==> (f . g) a 

Y así:

-- pull the t out on the rhs 
(\k t -> chr $ (a +) . flip mod 26 $ flip (-) (2*a) $ ((+) (ord k) . ord) t) 
-- flip (.) (using a section) 
(\k t -> chr $ (a +) . flip mod 26 $ flip (-) (2*a) $ ((. ord) $ (+) (ord k)) t) 
-- pull the k out 
(\k t -> chr $ (a +) . flip mod 26 $ flip (-) (2*a) $ ((. ord) . ((+) . ord)) k t) 

Ahora, tenemos que convertir todo a la izquierda de k y t en un gran término función, por lo que tenemos una expresión del formulario (\k t -> f k t). Aquí es donde las cosas se ponen un poco alucinantes. Para empezar, tenga en cuenta que todos los términos hasta el último $ son funciones con un único argumento, por lo que podemos componerlos:

(\k t -> chr . (a +) . flip mod 26 . flip (-) (2*a) $ ((. ord) . ((+) . ord)) k t) 

Ahora, tenemos una función del tipo Char -> Char -> Int que queremos componer con una función del tipo Int -> Char, produciendo una función del tipo Char -> Char -> Char. Podemos lograr que el uso de la (muy extraño de aspecto) regla

f (g a b) ==> ((f .) . g) a b 

Eso nos da:

(\k t -> (((chr . (a +) . flip mod 26 . flip (-) (2*a)) .) . ((. ord) . ((+) . ord))) k t) 

Ahora podemos simplemente aplicar una reducción beta:

((chr . (a +) . flip mod 26) .) . (flip flip (2*a) . ((-) .) . ((. ord) . (+) .ord)) 
+0

Usar las instancias '->' de Monad, Applicative o Arrow también son buenos trucos. – ephemient

+0

'f (g a) ==> f $ g a' realmente no ayuda. El lado derecho sigue siendo 'f $ (g a)'. Lo que quieres es composición de funciones. 'f (g a)' es '(fg) a'. – Prateek

3

Asumo que el objetivo de tu liberación de puntos es hacer que el código sea más conciso y más legible. Por lo tanto, creo que es aconsejable hacer algunas otras refactorizaciones hacia la simplificación, que luego podrían facilitar la eliminación de las variables.

(\k t -> chr $ a + flip mod 26 (ord k + ord t - 2*a)) 

En primer lugar, la flip es innecesaria:

(\k t -> chr $ a + (ord k + ord t - 2*a) `mod` 26) 

A continuación, me gustaría utilizar nombre y conquistar objeto de eliminar una función parcial de forma independiente utilizable:

encode_characters k t = chr $ encode (ord k) (ord t) 
encode x y = (x + y - 2*a) `mod` 26 + a 

también dio un nombre a la primera expresión para hacerlo más claro y reutilizable. encode_characters es ahora fácil de hacer sin punto utilizando la técnica de @Nefrubyr:

encode_characters = chr . encode `on` ord 

En cuanto a la segunda expresión, no puedo producir una forma que es más fácil de leer que cualquier muestra en las otras respuestas y todas son menos legible que la forma puntual. Por lo tanto, sugiero dejar de refactorizar en este punto y admirar la limpieza y reutilización del código resultante.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~

PD: como ejercicio, dependiendo del contexto del problema, una pequeña modificación de las interfaces de función (qué datos de qué forma se pasa a las funciones) podría producir más simplificaciones al generalizar el problema.

A. Implementar y simplificar la función encode_n_characters :: [Char] -> Char donde encode_characters k t = encode_n_characters [k, t]. ¿Es el resultado más simple que la función especializada de dos argumentos?

B. implementar una función de encode' se define a través de encode' (x + y) = encode x y y reimplementar encode_characters utilizando esta función. ¿Alguna de las funciones se vuelve más simple? ¿La implementación es más simple en general? ¿Es encode' más o menos reutilizable que encode?

Cuestiones relacionadas