CODEWITHSUNDEEP
haskellfunctional-programming
Marcus Johnson
Marcus Johnson

Reputation: 433

Is it possible to write a function that takes map, reduce, or filter and returns a 'functionised' version of them?

Forgive me my lack of proper terminology - I don't know anything about -morphisms, etc., but I have the feeling that the concept I am trying to express could be described by some term of that sort.

Map, reduce, and filter, the classical higher-order functions, all have the general structure of taking a function f and a list of data xs and doing something with that f to all the xs. Now, for each of them, I can imagine a 'functionised' version - call them mapf, reducef, and filterf - that instead takes a piece of data x and a list of functions fs and does each of the functions fs to the data x. Specifically, mapf would give you back a list of f1(x), f2(x), ..., reducef would give you f3 (f2 (f1 (x))) or f1 (f2 (f3 (x))) (depending on whether it was left or right), and filterf would test whether each of f1(x), f2(x), ... was true and return only the fs that were.

My question is this: is it possible to write a general function, functionise, that takes map, reduce, or filter as its argument and produces the corresponding mapf, reducef, or filterf function? (In an elegant way of course, not just as a series of case expressions.)

I don't mind what programming language is used; in my own experimentation I have been using Haskell, and what led me to this question was that I noticed that all three of the functions can be defined in a very similar way:

rev = \x y -> y x

mapf :: a -> [a -> b] -> [b]
mapf x fs = map (rev x) fs

reducef :: a -> [a -> a] -> a
reducef x fs = foldl rev x fs

filterf :: a -> [a -> Bool] -> [a -> Bool]
filterf x fs = filter (rev x) fs

I am tantalised by the similarity of them, so I'd like to either find out that it is possible, and to see how, or to be shown that it isn't possible, and see why. As I said, the programming language isn't crucial, so I don't mind if it's possible in language A but not in language B because of language B's type system - that'd be interesting.

Thank you!

Upvotes: 3

Views: 508

Answers (3)

Chris Kuklewicz
Chris Kuklewicz

Reputation: 8153

Your code looks similar to 'swing' which I found hidden in the wiki under pointfree.

swing f c a = f ($ a) c

swing map :: forall a b. [a -> b] -> a -> [b]
swing any :: forall a. [a -> Bool] -> a -> Bool
swing foldr :: forall a b. b -> a -> [a -> b -> b] -> b
swing zipWith :: forall a b c. [a -> b -> c] -> a -> [b] -> [c]
swing find :: forall a. [a -> Bool] -> a -> Maybe (a -> Bool)

-- applies each of the predicates to the given value, returning the first
-- predicate which succeeds, if any

swing partition :: forall a. [a -> Bool] -> a -> ([a -> Bool], [a -> Bool])

Upvotes: 3

Ingo
Ingo

Reputation: 36339

Not meaning to downplay your ideas, but it is hardly worth the effort. For instance to apply a list of functions to a value would be:

map ($ v) [f1, f2, f3]

Your mapf is just another specialization of map 

mapf :: v -> [(v -> a)] -> [a]
mapf v fs = map ($v) fs

Upvotes: 16

hammar
hammar

Reputation: 139870

reducef doesn't quite fit the same pattern as the other ones, but for map and filter, the pattern is \g x fs -> g (rev x) fs, or (. rev) for short:

> :t (. rev) map
(. rev) map :: a -> [a -> t] -> [t]
> :t (. rev) filter
(. rev) filter :: a -> [a -> Bool] -> [a -> Bool]

If you want to include reducef, you'll need a slightly different pattern, \g x fs -> g rev x fs, which can be shortened to ($ rev):

> :t ($ rev) foldl
($ rev) foldl :: t -> [t -> t] -> t

It won't work on map and filter directly, but you can use it on (map .) and (filter .):

> :t ($ rev) (map .)
($ rev) (map .) :: t1 -> [t1 -> t] -> [t]
> :t ($ rev) (filter .)
($ rev) (filter .) :: t1 -> [t1 -> Bool] -> [t1 -> Bool]

So I think functionalise = ($ rev) is about as close as you can get.

Upvotes: 5

Related Questions