I want to write a function which is similar to `flip` in Haskell to get rid of lambda expressions. But I can't deal with it's type

Question

I want to write a Haskell function which acts like flip but is far more general and can make any parameter of a function be the last parameter. For convenience, we use pull to represent it.

It is easy to write the following code:

Prelude> :t flip          --we just call this function a swap
flip :: (a -> b -> c) -> b -> a -> c
Prelude> :t (flip.)       --we just call this function a swap
(flip.) :: (a -> a1 -> b -> c) -> a -> b -> a1 -> c
Prelude> :t ((flip.).)    --we just call this function a swap
((flip.).) :: (a -> a1 -> a2 -> b -> c) -> a -> a1 -> b -> a2 -> c
Prelude> :t (((flip.).).) --we just call this function a swap
(((flip.).).)
  :: (a -> a1 -> a2 -> a3 -> b -> c) -> a -> a1 -> a2 -> b -> a3 -> c

And we find that with more (.) applied to flip, it can swap arbitrary adjacent pair of parameters. And with the above results we can write:

Prelude> :t flip
flip :: (a -> b -> c) -> b -> a -> c
Prelude> :t (flip.) . flip
(flip.) . flip :: (a1 -> a -> b -> c) -> a -> b -> a1 -> c
Prelude> :t ((flip.).) . (flip.) . flip
((flip.).) . (flip.) . flip
  :: (a2 -> a -> a1 -> b -> c) -> a -> a1 -> b -> a2 -> c
Prelude> :t (((flip.).).) . ((flip.).) . (flip.) . flip
(((flip.).).) . ((flip.).) . (flip.) . flip
  :: (a3 -> a -> a1 -> a2 -> b -> c) -> a -> a1 -> a2 -> b -> a3 -> c

We can find that with more swaps composed, it can pull an arbitrary parameter to the last place. So we can get rid of lambda expressions in many cases. But the above express is very bloated.

My main idea is to make a function pull to generalize the above functions. The pull acts roughly like bellow.

let f = undefined               --For convenience, we let f be undefined.

:t pull 0 (f::a->b->z)          --the type variable z is not a function type.
>pull 0 (f::a->b->z) :: b->a->z --pull is just like flip for 0 and a function of this type.
:t pull 0 (f::a->b->c->z)       --the type variable z is not a function type.
>pull 0 (f::a->b->c->z) :: b->c->a->z

:t pull 1 (f::a->b->c->z)       --the type variable z is not a function type.
>pull 1 (f::a->b->c->z) :: a->c->b->z
:t pull 1 (f::a->b->c->d->z)    --the type variable z is not a function type.
>pull 1 (f::a->b->c->d->z) :: a->c->d->b->z

:t pull 2 (f::a->b->c->d->z)    --the type variable z is not a function type.
>pull 2 (f::a->b->c->d->z) :: a->b->d->c->z
:t pull 2 (f::a->b->c->d->e->z) --the type variable z is not a function type.
>pull 2 (f::a->b->c->d->e->z) :: a->b->d->e->c->z

I tried many ways to do this. The naivest one is:

swap :: Word -> a -> a
swap 0 = flip
swap n = dot $ swap (n-1)

and ghc complained like bellow and I understand why:

-- Prelude> :reload
-- [1 of 1] Compiling Main             ( ModifyArbitrayParameterOfAFunction.hs, interpreted )
--
-- ModifyArbitrayParameterOfAFunction.hs:4:21:
--     Occurs check: cannot construct the infinite type: c0 = a1 -> c0
--     Expected type: (a1 -> c0) -> c0
--       Actual type: (a1 -> c0) -> a1 -> c0
--     In the return type of a call of `modify'
--     Probable cause: `modify' is applied to too few arguments
--     In the first argument of `(.)', namely `(modify (n - 1) modi)'
--     In the expression: (modify (n - 1) modi) . f1
--
-- ModifyArbitrayParameterOfAFunction.hs:4:42:
--     Occurs check: cannot construct the infinite type: c0 = a1 -> c0
--     Expected type: a1 -> a1 -> c0
--       Actual type: a1 -> c0
--     In the second argument of `(.)', namely `f1'
--     In the expression: (modify (n - 1) modi) . f1
--     In an equation for `modify':
--         modify n modi f1 = (modify (n - 1) modi) . f1
-- Failed, modules loaded: none.

Maybe my goal is just a wishful thinking, but considering Haskell's type system is even able to write lambda expressions, I dare to say there must be a way to do this.

Answer 1

As mentioned in the comments, you can't have a function to which you'd pass the arity of the function you want to flip. Parameters are computed at runtime, while you need the value at compile time so that you can determine the correct type.

Neither you can make it without passing it the arity somehow. For example a -> b -> c -> d could be viewed as a function of three arguments returning d, or as a function if two arguments returning c -> d.

Probably the easiest solution would be to define the functions explicitly, like flip2, flip3 etc. I know this isn't what you're looking for, but it's the most practical solution.

Another option would be to use Template Haskell. Then, the situation is different, because Template Haskell executes (I'd say "meta-") code at compile time. With TH you can create a function that takes a natural number and produces a TH expression that can be compiled into another module. The meta-function could be defined as

{-# LANGUAGE TemplateHaskell #-}
module GenFlipTH where

import Language.Haskell.TH

pull :: Int -> Q Exp
pull 0              = varE 'flip
pull n | n < 0      = fail "Negative arity"
       | otherwise  = [| fmap $(pull (n - 1)) . flip |]
-- Here we use the fact that `(->) r` is a functor.

and used in another module to generate the appropriate expression like

{-# LANGUAGE TemplateHaskell #-}
import GenFlipTH

flip3 :: (a -> b3 -> b2 -> b1 -> b -> c) -> (b3 -> b2 -> b1 -> b -> a -> c)
flip3 = $( pull 3 )

This is probably closes to your requirements I can get - you determine the function by a number and get compile-time guarantees that it's created and used correctly.

Answer 2

You can't do this as a normal function, because the type of the function will vary based on inputs. You can do it with the ad-hoc polymorphism introduced by typeclasses and functional dependencies. However, even then you will need a host of extensions to allow something like Oleg's IsFunction (see: http://okmij.org/ftp/Haskell/isFunction.lhs). That's the missing piece that lets you identify if you've reached the base case of the typeclass recursion.

Answer 3

If we did not have any limitations imposed by the type system, I would go for the following function, which moves the argument at position n to position m.

moveArg n m f =
  if n == 1 && m == 1 then f
  else if n > 1 && m > 1 then
    \x -> moveArg (n-1) (m-1) (f x)
  else if n == 1 then   -- Here m > 1
    moveArg 2 m (\x y -> f y x)
  else -- m == 1 && n > 1
    \x y -> (moveArg n 2 f) y x

You can easily implement this function in untyped languages (e.g. Javascript, Python). Note that:

flip == moveArg 1 2 == moveArg 2 1
moveArg 1 3 == \f a b c -> f b c a
moveArg 2 4 == \f a b c d -> f a c d b
etc.

However, I cannot find a language in which we could type such a function. For that we would need a way to programmatically create a dependent type signature for f that depends on n, m as constants, e.g.:

moveArg: (n: Int) -> (m: Int) -> mkArgSubstitution n m

where it would not be hard to write a program mkArgSubstitution that computes types, such as:

mkArgSubstitution 1 2 = forall a b c. (a -> b -> c) -> (b -> a -> c)
mkArgSubstitution 2 4 = forall a b c d e. (a -> b -> c -> d -> e) -> (a -> c -> d -> b -> e)
...