Combine m-ary function with n-ary function in a single (m+n)-ary function returning the pair of their results

Question

I have no idea how useful the application would be, but I got curious about it because of this C++ answer to a question of mine.

So, given, say, a ternary f and a binary g, e.g.

f x y z = x + 10*y + 100*z
g x y = x + 10*y

how can I get a function h such that the following holds?

h f g 1 2 3 4 5 == (321, 54)

Clearly I can define

h f g = \x y z v w -> (f x y z, g v w)

But I was curious to know if it could be done in point-free style for every arities m and n, using some existing abstraction.

For this specific example (m == 3 && n == 2) pointfree.io shows that the result becomes unreadable:

h = flip . ((flip . ((flip . (((.) . (.) . (,)) .)) .)) .)

but I'm still curious if something else exists.

For fun, I've tried to apply combinatory logic mecanically to derive a formula, but still only for the specific case of m == 3 && n == 2:

b = (.)  -- bluebird (names from "To Mock a Mockingbird")
c = flip -- cardinal (names from "To Mock a Mockingbird")
p = (,)
f x y z = x + 10*y + 100*z
g x y = x + 10*y
{-
p(fxyz)(gvw) = ?xyzvw, with ? in terms of p, f, g and known birds
(p(fxyz))(gvw)
B(B(p(fxyz)))gvw
CBg(B(p(fxyz)))vw
B(CBg)B(p(fxyz))vw
B(B(CBg)B)p(fxyz)vw
B(B(B(CBg)B)p)(fxy)zvw
B(B(B(B(CBg)B)p))(fx)yzvw
B(B(B(B(B(CBg)B)p)))fxyzvw
B(B(B(B(B(CBB)(CB)g)p)))fxyzvw
B(B(B(BB(B(CBB)(CB))gp)))fxyzvw
B(B(BB(BB(B(CBB)(CB))g)p))fxyzvw
B(B(B(BB)(BB(B(CBB)(CB)))gp))fxyzvw
B(BB(B(BB)(BB(B(CBB)(CB)))g)p)fxyzvw
BB(BB(B(BB)(BB(B(CBB)(CB)))g))pfxyzvw
B(BB)(B(BB)(B(BB)(BB(B(CBB)(CB)))))gpfxyzvw
C(C(B(BB)(B(BB)(B(BB)(BB(B(CBB)(CB))))))p)fgxyzvw
-}
h = c (c (b (b b) (b (b b) (b (b b) (b b (b (c b b) (c b)))))) p)
h f g 1 2 3 4 5 == (321, 54) -- True

there are no *m*-ary functions in Haskell: each function takes *exactly* one parameter. — Willem Van Onsem, Apr 03 '23 at 20:16
the main problem is that, depending on the instance of a typeclass for example, something can be a function or not. So one can not know, for example through the syntax, how many parameters there are. The fact that a function has only one parameter is not an "implementation detail", it is quite fundamental. — Willem Van Onsem, Apr 03 '23 at 21:57
Take for example `printf` that is in some sense a "*variadic*" function, because through the typeclass the result can be either a `String`, `IO String`, or a function that maps to some other item: https://hackage.haskell.org/package/base-4.18.0.0/docs/Text-Printf.html#v:printf — Willem Van Onsem, Apr 03 '23 at 22:27
The usual "categorical" approach would be to use `uncurry` so to convert an "n-ary" function into a function taking a big tuple, then using something like `h1 &&& h2` together with some `curry` (and projections to discard unneeded inputs). This is more or less how to define the semantics of the simply-typed lambda calculus in a Cartesian closed category. — chi, Apr 05 '23 at 15:24
@chi, but `uncurry` uncurries only one argument, so I'd still have the problem of how many times to apply it, no? — Enlico, Apr 05 '23 at 15:34
@Enlico Yes, you need to use the "right" curry which depends on the arity. As the answers below explain, there can not be a truly arity-independent solution. — chi, Apr 05 '23 at 20:58

score 3 · Answer 1 · answered Apr 04 '23 at 03:29

As Willem Van Onsem points out in the comments, the problem with your question is that, technically, every function in Haskell takes exactly one parameter. I know what you mean, and I know what you want to do, but there's no reason why (+) can't just be a one argument function that returns a function and not a two argument function. Indeed, if we define a Num instance for something like Int -> Int, then it's totally possible that (+) is a 3 argument function!

On the other hand, just because the number of arguments can't be inferred, it doesn't mean that you're doomed. If you're okay with giving GHC a few hints, you can do what you want at the type level. Consider the following:

data Nat = Zero | Succ Nat
type One = Succ Zero
type Two = Succ One
type Three = Succ Two
type Four = Succ Three

class NFun m n f g where
  type family FunT m n f g
  h :: f -> g -> FunT m n f g

instance NFun m n x y => NFun (Succ m) n (a -> x) y where
  type FunT (Succ m) n (a -> x) y = a -> FunT m n x y
  h f g a = h @m @n (f a) g

instance NFun Zero n x y => NFun Zero (Succ n) x (a -> y) where
  type FunT Zero (Succ n) x (a -> y) = a -> FunT Zero n x y
  h f g a = h @Zero @n f (g a)

instance NFun Zero Zero x y where
  type FunT Zero Zero x y = (x,y)
  h = (,)

(This can probably be done prettier using GHC's TypeLits, but I always have a little trouble getting the induction to work out, so I rolled the natural numbers myself.)

Here, I've defined a type class NFun that takes two numeric types that indicate how many arguments the functions will take. The first instance provides arguments to the first function, and the second instance provides arguments to the second function. The final instance pairs up the results.

You can use it like this:

f x y z = x + 10*y + 100*z
g x y = x + 10*y

h @Three @Two f g 1 2 3 4 5 == (321, 54)

Can you show what _if we define a Num instance for something like Int -> Int, then it's totally possible that (+) is a 3 argument function!_ means? — Enlico, Apr 04 '23 at 06:01
@Enlico: `(+)` has type `Num a => a -> a -> a`. If I deifne `instance Num ((->) b b)` in some way, then there is a function `(+) :: (b -> b) -> (b -> b) -> (b -> b)` or `(+) :: (b -> b) -> (b -> b) -> b -> b`, a function that takes thus two functions as parameter, and returns a function that will thus take the third parameter. — Willem Van Onsem, Apr 04 '23 at 10:58
For a specific case, I can define `instance Num (a -> Integer) where (+) = liftA2 (+); fromInteger = const`. Then, `3 + 4` is a function that consumes a value and produces `7`. In other words, there's an instance where `(+)` is a function of three arguments. — DDub, Apr 05 '23 at 19:39

score 2 · Accepted Answer · answered Apr 05 '23 at 15:12

Unless the function is a concrete type, the arity of the function (if we leave out the fact that strictly speaking each function has an arity of one), can be variable. Indeed, a good example is printf :: PrintfType r => String -> r.

This seems a simple function. But there is a problem: r here can be any instance of PrintfType, and we have as instances:

instance PrintfType a ~ () => PrintfType (IO a) where
    -- ...

instance IsChar c => PrintfType [c] where
    -- ...

instance (PrintfArg a, PrintfType r) => PrintfType (a -> r) where
    -- ...

The first two are not that interesting. The last one is. Indeed, it means that it can return another function.

Which means that one can use printf as:

printf "foo"             :: String
printf "foo %i" 14       :: String
printf "foo %i %i" 14 25 :: String

They this implemented some sort of variadic function where the number of parameters depends on how you use printf.

While I'm not entirely happy with printf since it is not very "safe" compared to a lot of other Haskell functions, it demonstrates how one can make variadic functions. For example one can pass too many or too few parameters, and %i is not guaranteed ot retrieve an integer or number-like value, so there are better ways to format strings.

But regardless, the number of parameters does not depend on the function itself, so you can not derive this from the function's point of view, but from how it is used. Therefore, unless the types are all concrete in a function, if typeclasses are used, it is no longer easy to determine the arity of the function and therefore thus "merge" two functions together.

What do you mean by _it is not very "safe" compared to a lot of other Haskell functions_? What's unsafe about it? If it takes long to answer, I can ask another ad-hoc question. Unless you have a link to an existing one. — Enlico, Apr 20 '23 at 07:12
@Enlico: it is not said that the number of parameters matches in the string with the number of parameters, or that the types match, like `printf "foo %s %s bar" "qux"` has an extra `%s`, or `printf "foo" 42`, or you can pass a string that is the formatted with `%i`. — Willem Van Onsem, Apr 20 '23 at 07:25

Combine m-ary function with n-ary function in a single (m+n)-ary function returning the pair of their results

2 Answers2