Is it possible to implement this function?

Question

I want to have a function q of type:

q :: ([b] -> b) -> ([(a, b)] -> (a, b))

which takes a function that selects a single element from a list, and lifts* that function into the context of selecting a single pair from a pair of lists (completely ignoring the first element of the pairs).

Is it even possible to write such a function? I haven't been able to make any progress on this.

_{*is 'lift' the right word?}

---

Example use: if I have a function:

safeMaximum :: b -> [b] -> b

> safeMaximum 18 [] 
18
> safeMaximum 18 [4,5,1,4,3]
5

I then want to use safeMaximum to get, from a list of pairs, the pair whose 2nd element is the largest:

liftedSafeMaximum :: (a, b) -> [(a, b)] -> (a, b)
liftedSafeMaximum val = q val safeMaximum

liftedSafeMaximum ("?", 3) []
> ("?", 3)
liftedSafeMaximum ("?", 3) [("xyz", 1), ("123", 3), ("hi", 2)]
> ("123", 3)

Answer 1

You can get something like this to work if you're willing to refine your definition of a selector function slightly. Instead of selecting an element from a list directly, we will have a polymorphic function that, given a projection that allows it to look at the part of each element it's interested in, will select an item from a list.

All q has to do then, is give it snd as the projection to use.

{-# LANGUAGE Rank2Types #-}

import Data.Ord (comparing)
import Data.List (maximumBy)

q :: (forall c. (c -> b) -> c -> [c] -> c) -> (a, b) -> [(a, b)] -> (a, b)
q select = select snd

safeMaximumOn :: Ord b => (a -> b) -> a -> [a] -> a
safeMaximumOn proj x xs = maximumBy (comparing proj) (x:xs)

liftedSafeMaximum :: Ord b => (a, b) -> [(a, b)] -> (a, b)
liftedSafeMaximum = q safeMaximumOn

This is essentially the same idea from a previous answer of mine.

Answer 2

You describe this as wanting to "lift a function into a context", so let's see what that works out to mean. Starting from the desired type:

q :: (a, b) -> ([b] -> b) -> ([(a, b)] -> (a, b))

...we can optimistically abstract over the desired context:

q :: f b -> ([b] -> b) -> ([f b] -> f b)

Assuming that f is a Functor--which it is, in the motivating example--we could lift [b] -> b to f [b] -> f b. We could get from that to the desired type if we had a function of type [f b] -> f [b], which looks a lot like sequence.

Consider the case where f is ((->) a) instead: given a function [b] -> b and a list [a -> b], we can return a function a -> b that applies its argument of type a to every function in the list, uses the selector function, then returns the result of type b. That sounds like what you're after!

Unfortunately it doesn't work for your specific example--the Monad involved is the writer monad, which would add a Monoid constraint on a and always return the monoid sum of every a value in the list.

The reason it fails is that we have only an opaque selection function for b values, which by necessity must be used without any context, which entails using something like sequence to extract (and in the process merge) all the individual contexts. To write the function you want, you'd need a way to merge contexts without losing information associating a context to each element.

The reader monad works where others don't because the "merge" process involved is unique--applying a single argument to multiple functions is based on a contravariant use of the canonical comonoid given by \x -> () and \x -> (x, x), where each result element uniquely determines the original input.

To get the same property in covariant position, we would need a monoid where each input element uniquely determines the resulting sum, which implies that every input must be the same, which implies that they must be of a type with only one value. Based on that, we can indeed write a version of your function with a slightly more restricted type:

q' :: ([b] -> b) -> ([((), b)] -> ((), b))

But I suppose that's not very satisfying. :]