haskell - 我想在 Haskell 中编写一个类似于 `flip` 的函数来摆脱 lambda 表达式。但我无法处理它的类型

Question

我想编写一个 Haskell 函数，它的作用类似于翻转，但更通用，可以使函数的任何参数成为最后一个参数。为方便起见，我们使用 pull来代表它。

编写以下代码很容易:

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

我们发现，将 more (.) 应用于翻转，它可以交换任意相邻的参数对。有了上面的结果，我们可以写:

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

我们可以发现，随着更多的交换组合，它可以将任意参数拉到最后一个位置。所以我们可以在很多情况下摆脱 lambda 表达式。但是上面的 express 很臃肿。

我的主要想法是制作一个函数 pull概括上述功能。 pull行为
大致如下。

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

我尝试了很多方法来做到这一点。最天真的是:

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

和 ghc 提示如下，我明白为什么:

-- 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.

也许我的目标只是一厢情愿，但考虑到 Haskell 的类型系统甚至可以编写 lambda 表达式，我敢说一定有办法做到这一点。

Answer 1

您不能将其作为普通函数执行，因为函数的类型会因输入而异。您可以使用类型类和功能依赖项引入的临时多态性来做到这一点。然而，即便如此，您仍需要大量扩展来允许像 Oleg 的 IsFunction 这样的东西。 (见:http://okmij.org/ftp/Haskell/isFunction.lhs)。那是缺少的部分，可以让您确定是否已达到类型类递归的基本情况。