¿Qué es un esquema general para escribir una función en estilo pointfree?

Question

Estoy trabajando a través del 20 Intermediate Haskell Exercises en este momento, lo cual es un ejercicio bastante divertido. Implica la implementación de varias instancias de las clases de tipos Functor y Monad (y funciones que toman Functor sy Monad s como argumentos) pero con lindos nombres como Furry y Misty para disfrazar lo que estamos haciendo (un código interesante).

He estado tratando de hacer algo de esto en un estilo libre de puntos, y me pregunto si hay un esquema general para convertir una definición de punto (?) En una definición libre de puntos. Por ejemplo, esta es la clase de tipos de Misty:

class Misty m where 
    unicorn :: a -> m a 
    banana :: (a -> m b) -> m a -> m b 

(las funciones unicorn y banana son return y >>=, en caso de que no es obvio) y aquí está mi aplicación de apple (equivalente a flip ap):

apple :: (Misty m) => m a -> m (a -> b) -> m b 
apple x f = banana (\g -> banana (unicorn . g) x) f 

partes posteriores de los ejercicios tienen que implemente versiones de liftM, liftM2 etc. Aquí están mis soluciones:

appleTurnover :: (Misty m) => m (a -> b) -> m a -> m b 
appleTurnover = flip apple 

banana1 :: (Misty m) => (a -> b) -> m a -> m b 
banana1 = appleTurnover . unicorn 

banana2 :: (Misty m) => (a -> b -> c) -> m a -> m b -> m c 
banana2 f = appleTurnover . banana1 f 

banana3 :: (Misty m) => (a -> b -> c -> d) -> m a -> m b -> m c -> m d 
banana3 f x = appleTurnover . banana2 f x 

banana4 :: (Misty m) => (a -> b -> c -> d -> e) -> m a -> m b -> m c -> m d -> m e 
banana4 f x y = appleTurnover . banana3 f x y 

Ahora, banana1 (equivalente a liftM o fmap) que era capaz de poner en práctica en el estilo pointfree, mediante una definición adecuada de appleTurnover. Pero con las otras tres funciones he tenido que usar parámetros.

Mi pregunta es: ¿Existe alguna fórmula para convertir definiciones como estas en definiciones sin puntos?

Answer 1

Como lo demuestra la utilidad pointfree, es posible realizar cualquier conversión de este tipo automáticamente. Sin embargo, el resultado es más a menudo ofuscado que mejorado. Si el objetivo es mejorar la legibilidad en lugar de destruirla, entonces el primer objetivo debería ser identificar por qué una expresión tiene una estructura particular, encuentra una abstracción adecuada y crea cosas de esa manera.

La estructura más simple es simplemente encadenar cosas juntas en una tubería lineal, que es la composición de funciones simples. Esto nos lleva bastante lejos por sí solo, pero como notó, no maneja todo.

Una generalización es para funciones con argumentos adicionales, que se pueden construir de forma incremental. Aquí hay un ejemplo: Defina onResult = (. (.)).Ahora, aplicar onResult n veces a un valor inicial de id le da composición de funciones con el resultado de una función n-aria. Entonces podemos definir comp2 = onResult (.), y luego escribir comp2 not (&&) para definir una operación NAND.

Otra generalización, que abarca lo anterior, en realidad, es definir operadores que aplican una función a un componente de un valor mayor. Un ejemplo aquí sería first y second en Control.Arrow, que funcionan en 2 tuplas. Conal Elliott's Semantic Editor Combinators se basan en este enfoque.

Un poco diferente es el caso cuando se tiene una función multi-argumento en algún tipo b, y una función de a -> b, y la necesidad de combinarlos en una función multi-argumento usando a. Para el caso común de las funciones 2-ary, el módulo Data.Function proporciona el combinador on, que puede usar para escribir expresiones como compare `on` fst para comparar 2-tuplas en sus primeros elementos.

Es un problema más complicado cuando se usa un solo argumento más de una vez, pero aquí también se pueden extraer patrones recurrentes significativos que también se pueden extraer. Un caso común aquí es aplicar múltiples funciones a un único argumento, luego recolectar los resultados con otra función. Esto sucede para corresponderse con la instancia Applicative para funciones, que nos permite escribir expresiones como (&&) <$> (> 3) <*> (< 9) para verificar si un número cae en un rango determinado.

Lo importante, si desea utilizar algo de esto en el código real, es pensar en qué significa la expresión y cómo eso se refleja en la estructura. Si lo hace, y luego lo refactoriza en estilo libre de puntos utilizando combinadores significativos, a menudo hará que la intención del código sea más clara de lo que sería de otra manera, a diferencia de la salida típica de pointfree.

Answer 2

Sí! Uno de los trucos es escribir sus puntos en notación de prefijo en lugar de infijo. Entonces debería poder encontrar cosas nuevas que se parezcan a la composición de funciones. He aquí un ejemplo:

banana2 f = appleTurnover . banana1 f 
      = (.) appleTurnover (banana1 f) 
      = ((.) appleTurnOver) . banana1 $ f 
banana2 = (appleTurnover .) . banana1 

El código fuente de la utilidad pointfree contiene más, pero éste maneja una gran cantidad de casos.

banana4 f x y = appleTurnover . banana3 f x y 
       = (.) appleTurnover ((banana3 f x) y) 
       = ((.) appleTurnover) . (banana3 f x) $ y 
banana4 f x = ((.) appleTurnover) . (banana3 f x) 
      = (.) ((.) appleTurnover) (banana3 f x) 
      = ((.) ((.) appleTurnover)) ((banana3 f) x) 
      = ((.) ((.) appleTurnover)) . (banana3 f) $ x 
banana4 f = ((.) ((.) appleTurnover)) . (banana3 f) 
      = (.) ((.) ((.) appleTurnover)) (banana3 f) 
      = ((.) ((.) ((.) appleTurnover))) (banana3 f) 
      = ((.) ((.) ((.) appleTurnover))) . banana3 $ f 
banana4 = ((.) ((.) ((.) appleTurnover))) . banana3 
     = (((appleTurnover .) .) .) . banana3 

Answer 3

hay un paquete pointfree que tiene una definición de función Haskell y los intentos de volver a escribir en un estilo pointfree. Sugeriría experimentar con esto para obtener nuevas ideas. Vea this page para más detalles; el paquete está disponible here.

Answer 4

que utilice el siguiente término sistema de reescritura:

\x -> f x ------> f 
f y x ----------> flip f x y 
\x -> f (g x) --> f . g 

Está incompleto (leer por qué en los libros sobre lógica combinatoria), pero es suficiente:

Aquí es banana2:

banana2 f = appleTurnover . banana1 f 

Reescriba como un lambda:

banana2 = \f -> appleTurnover . banana1 f 

Escribir en el estilo de prefijo (.):

banana2 = \f -> (.) appleTurnover (banana1 f) 

Tenga en cuenta que

banana2 = \f -> ((.) appleTurnover) (banana1 f) 

Así que la regla 3 se pueden aplicar.f es (.) appleTurnover y g es banana:

banana2 = ((.) appleTurnover) . banana1 

Answer 5

Desde el estilo pointfree es combinadores estilo, sólo se aplica conocidos definiciones combinadores, leerlos imposible para hacer la sustitución:

B f g x = f (g x)  -- (.) , <$> for ((->) a) 
C f x y = f y x  -- flip 
K x y = x    -- const 
I x = x    -- id 
S f g x = f x (g x) -- <*> , ap for ((->) a) 
W f x = f x x   -- join 
(f >>= g) x = g (f x) x 
(f =<< g) x = f (g x) x 

A veces liftMx, liftAx, sequence , sequenceA puede simplificar las cosas. También consideraría foldr, unfoldr, iterate, until etc. como combinadores básicos.

A menudo, el uso de secciones operador también ayuda:

op a b = (a `op` b) = (`op` b) a = (a `op`) b 

Algunos patrones pueden familiarizarse y así, utilizar directamente:

((f .) . g) x y = f (g x y) 
((. f) . g) x y = g x (f y) 

(((f .) .) . g) x y z = (f .) (g x y) z = f (g x y z) 
(((. f) .) . g) x y z = (. f) (g x y) z = g x y (f z) 

etc.