Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Employing arrows to fold a list of tuples

Sometimes you want to fold a list of tuples into one tuple using different folding functions. For instance, in order to glue together a list of runState results, getting an (in some sense) combined state and a combined result.

Consider the following implementation:

wish :: (a -> a' -> a) -> (b -> b' -> b) -> (a,b) -> [(a', b')] -> (a,b)
wish lfn rfn x xs = foldl (\(a,b) -> (lfn a) *** (rfn b)) x xs

Although it works, I feel uncomfortable about this lambda. lfn *** rfn by itself has a type of (a,b) -> (a -> a', b -> b'), which I can't find a way to properly apply to a tuple without ever resorting to pattern matching. Is there a clear and elegant way I'm missing? It could be a library function of type (a,a') -> (a -> a, a' -> a') -> (a, a') or a whole different approach, maybe.

like image 894
Francis Drake Avatar asked May 21 '13 18:05

Francis Drake


1 Answers

Control.Arrow does not pay much attention to higher-arity functions. What you really want is a function foo :: (a -> a' -> a'') -> (b -> b' -> b'') -> (a,b) -> (a',b') -> (a'',b''), the analogue of (***) for functions of arity 2. There is such a function in Data.Biapplicative (from the package bifunctor), which has the somewhat more general signature biliftA2 :: Biapplicative w => (a -> b -> c) -> (d -> e -> f) -> w a d -> w b e -> w c f. Since there is a Biapplicative instance for two-element tuples, that is all you need.

The only complaint I can see against your code as it stands is that it the currying of the lambda is non-obvious; I might prefer the more explicit \(a,b) (a',b') -> (lfn a a', rfn b b').

Edit notes: I had concluded that the needed function did not exist, and suggested defining it; spurred by Carl's comment, I found the one in Biapplicative (the more general type signature had prevented Hoogle from finding it under my suggested signature).

like image 62
isturdy Avatar answered Oct 22 '22 00:10

isturdy