haskell - ¿En qué se diferencia un transductor de una función parcialmente aplicada?

clojure transducer

Question

Después de leer este artículo en Clojure ( http://blog.podsnap.com/ducers2.html ) presentando transductores, estoy confundido sobre qué es un transductor. ¿Es un map parcialmente aplicado en Haskell, como el map (+1) un transductor? Al principio pensé que esta era una forma Clojure de usar una aplicación parcial, pero luego el artículo continúa implementándola en Haskell con un tipo explícito. ¿Qué uso tiene en Haskell?

Answer 1

En Clojure (map inc) es un transductor, pero no en Haskell, porque Haskell tiene que obedecer al currying, pero un Lisp sin tipo puede romper esa convención de curry por defecto. El tipo de transductores es en cambio:

type Transducer a b = forall r . (b -> r -> r) -> (a -> r -> r)

Decimos que el transductor ''convierte a en b ''. Sí, la a y la b parecen "hacia atrás" en el lado derecho. El concepto significa que un transductor debe dejar r como una variable de tipo general, pero está totalmente autorizado para especializarse en a y b .

Permítanme revertir dos de los argumentos en foldr:

-- cf. with foldr :: (x -> r -> r) -> r -> [x] -> r
ffoldr :: (x -> r -> r) -> [x] -> r -> r
ffoldr = flip . foldr

(también podemos usar foldl pero tenderá a invertir las cosas más tarde). Esto significa que se puede usar un Transducer para transformar el primer argumento de ffoldr de x y , de este modo, podemos procesar un [x] con y -> r -> r usando foldr . Los transductores se encuentran entre las entradas ([x], r) y el procesador final (y, r) -> r .

He volteado los segundos dos argumentos para enfatizar también que, sorprendentemente, ffoldr :: Transducer [x] x . Al usar la simetría de los argumentos, también tenemos una composición genérica de transductores, que simplemente es composición de funciones:

(.) :: Transducer a b -> Transducer b c -> Transducer a c

(Si crees que es genial que dar estos términos para todos nos permite revertir la forma en que normalmente utilizas . , Puedes hacerlo arbitrariamente a través de una técnica llamada "continuación de aprobación").

Por ejemplo, aquí está el transductor de filtro:

tfilter :: (a -> Bool) -> (a -> r -> r) -> a -> r -> r
-- or: (a -> Bool) -> Transducer a a
tfilter predicate f a = if predicate a then f a else id

Esto aplica la función de reducción f a r solo si el predicado se cumple. También hay un transductor de mapeo:

tmap :: (a -> b) -> (b -> r -> r) -> a -> r -> r
tmap ba f a = f (ba a)

Esto proporciona una semántica composable de mapa / filtro para cualquier tipo ''transducable'': un mapa / filtro fn puede funcionar para múltiples contextos.

El tipo Transductor tiene un lindo isomorfismo: resulta que el foldr de una lista para todo forall r. (x -> r -> r) -> r -> r forall r. (x -> r -> r) -> r -> r es perfectamente equivalente a esa lista [x] (es la "codificación de la Iglesia" de esa lista), y por lo tanto intercambiando el argumento a al frente del transductor definición nos da el tipo de letra (IMO mucho más fácil de entender!) type TransL ab = a -> [b] . Y esto es mucho más fácil de entender:

tl_map f = /a -> [f a]
tl_filter predicate = /a -> if predicate a then [a] else []

Para ejecutar estos en una lista, use concatMap ... que simplemente es >>= Entonces, simplemente escribe collection >>= transducer y tienes la colección transducida. El significado de TransL ab es, entonces, "tomar cada elemento de la lista original de a , y darme 0 o más elementos de tipo b para empalmar en mi lista saliente". Filtra empalmando 0 elementos cuando el predicado no funciona; se correlaciona produciendo 1 elemento de salida para cada elemento de entrada; otra operación tl_dupe = /a -> [a, a] es un transductor que duplica los elementos en una lista, [1,2,3] >>= tl_dupe convierte en [1,1,2,2,3,3] .

Donde foldr parece ser un Transducer [x] x ahora se ve que es idéntico a id :: TransL [x] x que tiene una forma de simplemente realizar una operación concat en medio de un cálculo; la función de identidad en este álgebra es en realidad return = /a -> [a] , también escrita (:[]) . La única pérdida es que ya no podemos usar . para componer estos, pero de hecho, la misma composición se proporciona en Control.Monad como el operador de composición de Kleisli >=> .

En resumen, los transductores son funciones a -> [b] hábilmente transformadas con un poco de codificación Church para que el operador de composición de Kleisli para estas flechas de Kleisli de la lista de mónadas se convierta simplemente en (.) .