Transducer: Composition, Abstraction, Performance
Higher-order functions like map , fold , filter are indispensable in any functional program. With their flexibility, they are the tool of choice for operations on collections of all kinds. However, their scope of application is not limited to classic lists or vectors. In this article, we examine more fundamental properties of these operations and take a particular look at so-called transducers in the Clojure programming language.
Additionally, we will see how we can achieve not only very good reusability but also higher performance with the help of meaningful abstraction.
Everything is a fold
Those who have engaged with functional programming in the past may already be familiar with this statement. If you haven‘t had the opportunity yet (or want to refresh your memory), let‘s first look at a variant of the usual definitions of map and filter . (Note: All examples are written in Clojure, so from this point on we‘ll call fold by its Clojure name reduce ):
( defn map "Takes a function f and applies it to every element of xs." [ f xs ] ( if ( empty? xs ) xs ( cons ( f ( first xs )) ( map f ( rest xs ))))) ( defn filter "Takes a predicate pred and returns a list with all elements of xs that satisfy pred." [ pred xs ] ( if ( empty? xs ) xs ( if ( pred ( first xs )) ( cons ( first xs ) ( filter pred ( rest xs ))) ( filter pred ( rest xs )))))
Many definitions can be found like this in various standard libraries. As the heading of this section already reveals, both functions can also be defined via fold (or rather reduce ). The signature of reduce , expressed in Haskell notation, looks like this: (b -> a -> b) -> b -> [a] -> b (specialized for lists in this case).
( defn mapping "Takes a function f and returns a function. The returned function takes a collection acc and an element x and appends x applied to f to the end of acc." [ f ] ( fn [ acc x ] ( conj acc ( f x )))) ( defn map "Takes a function f and applies it to every element of xs." [ f xs ] ( reduce ( mapping f ) [] xs )) ( defn filtering "Takes a predicate pred and returns a function. The returned function takes a collection acc and an element x and appends x to the end of acc if it satisfies pred." [ pred ] ( fn [ acc x ] ( if ( pred x ) ( conj acc x ) acc ))) ( defn filter "Takes a predicate pred and returns a list with all elements of xs that satisfy pred." [ pred xs ] ( reduce ( filtering pred ) [] xs ))
If our programs consisted exclusively of list processing, we could stop here, satisfied. However, something catches the eye: apart from the call to conj , the definitions of mapping and filtering tell us nothing about them working „only“ on collections!
From Collections to Processes
... continue reading