我想在Haskell中编写一个类似于`flip`的函数来摆脱lambda表达式.但我不能处理它的类型

Question

我想编写一个Haskell函数,它的作用类似于flip,但更通用,可以使函数的任何参数成为最后一个参数.为方便起见,我们用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

我们发现,如果将更多(.)应用于翻转,它可以交换任意相邻的参数对.通过以上结果我们可以写:

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表达式.但上面的表达非常臃肿.

我的主要想法是创建一个函数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

正如评论中提到的，您不能将要翻转的函数的参数传递给函数。参数是在运行时计算的，而您需要在编译时获得值，以便确定正确的类型。

如果不以某种方式传递参数，你就无法做到这一点。例如，a -> b -> c -> d可以将其视为返回 3 个参数的函数d，或者如果返回 2 个参数，则将其视为函数c -> d。

可能最简单的解决方案是显式定义函数，例如等flip2。flip3我知道这不是您正在寻找的，但它是最实用的解决方案。

另一种选择是使用 Template Haskell。然后，情况就不同了，因为 Template Haskell 在编译时执行（我会说“元”）代码。使用 TH，您可以创建一个函数，该函数采用自然数并生成可编译到另一个模块中的 TH 表达式。元函数可以定义为

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

并在另一个模块中使用来生成适当的表达式，例如

{-# LANGUAGE TemplateHaskell #-}
import GenFlipTH

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

这可能接近我能得到的您的要求 - 您通过数字确定函数并获得编译时保证它被正确创建和使用。