如何定义多元箭头？

Question

这个问题与有些相关：

我正在尝试定义几个半依赖类型，它们允许您跟踪函数的 'monotonicity'（如 Monotonicity Types 论文中所述），这样程序员就不会必须手动执行此操作（并且在将非单调操作传递给需要单调操作的对象时在编译时失败）。

更一般地说：我想跟踪一些 'qualifiers' 函数

基于，我已经能够定义'indexed category'和'indexed arrow'，其中h = f >>> g中h的限定符取决于限定符f 和 g.

这很有效，只要您只使用单参数函数。但是，（普通箭头也有这个问题），当您尝试创建具有多个参数的箭头时，您有以下选项。（以(+) :: Int -> Int -> Int为例）：

普通 arr (+)。其结果类型将为 Arrow x => x Int (Int -> Int)，因为该函数已柯里化。这意味着只有第一个参数被提升到箭头上下文中，因为箭头 'returns a function with one parameter less'。换句话说：箭头上下文不用于其余参数，所以这不是我们想要的。
arr (uncurry (+))。结果类型为 Arrow x => x (Int, Int) Int。现在这两个参数都已成为箭头的一部分，但我们失去了例如部分应用它。我也不清楚如何以与 arity 无关的方式进行 uncurrying：如果我们想要三、四、五……参数函数怎么办？

我知道可以定义一个 'recursive typeclass' 来创建一个多元函数，例如 Rosettacode here 中描述的实例。我试图定义一个可能以这种方式工作的更通用的函数包装类型，但到目前为止我还没有成功。我不知道如何在 a -> b 的类型类实例中正确辨别 b 是最终结果还是另一个函数 (b' -> c)，以及如何提取和使用 b' 的限定符] 如果结果是第二种情况

这可能吗？我在这里错过了什么吗？还是我完全走错了路，还有另一种方法可以将 n-argument 函数提升为箭头，而不管 n 的值如何？

Answer 1

下面是如何定义 arrowfy 以将函数 a -> b -> ... 转换为箭头 a `r` b `r` ...（其中 r :: Type -> Type -> Type 是您的箭头类型），以及函数 uncurry_ 将一个函数变成一个带有单个元组参数 (a, (b, ...)) -> z 的函数（然后可以使用 arr :: (u -> v) -> r u v 将其提升到任意箭头）。

{-# LANGUAGE
    AllowAmbiguousTypes,
    FlexibleContexts,
    FlexibleInstances,
    MultiParamTypeClasses,
    UndecidableInstances,
    TypeApplications
  #-}

import Control.Category hiding ((.), id)
import Control.Arrow
import Data.Kind (Type)

两种方法都使用具有重叠实例的多参数类型 class。一个函数实例，只要初始类型是函数类型就会被选中，一个基本情况实例，只要它不是函数类型就会被选中。

-- Turn (a -> (b -> (c -> ...))) into (a `r` (b `r` (c `r` ...)))
class Arrowfy (r :: Type -> Type -> Type) x y where
  arrowfy :: x -> y

instance {-# OVERLAPPING #-} (Arrow r, Arrowfy r b z, y ~ r a z) => Arrowfy r (a -> b) y where
  arrowfy f = arr (arrowfy @r @b @z . f)

instance (x ~ y) => Arrowfy r x y where
  arrowfy = id

关于 `arrowfy @r @b @z` 语法的附注

这是 TypeApplications 语法，自 GHC 8.0 起可用。

arrowfy 的类型是：

arrowfy :: forall r x y. Arrowfy r x y => x -> y

问题是r是有歧义的：在一个表达式中，上下文只能确定x和y，而这并不一定限制r。 @r 注释允许我们显式特化 arrowfy。请注意，arrowfy 的类型参数必须以固定顺序出现：

arrowfy :: forall r x y. ...

arrowfy @r1 @b @z             -- r = r1, x = b, y = z

(GHC user guide on TypeApplications)

现在，例如，如果你有一个箭头 (:->)，你可以这样写把它变成一个箭头：

test :: Int :-> (Int :-> Int)
test = arrowfy (+)

对于uncurry_，有一个额外的小技巧，这样n-argument函数就变成了n-tuple上的函数，而不是（n+1）元组被一个单元封顶你会天真地得到。这两个实例现在都按函数类型索引，实际测试的是结果类型是否为函数。

-- Turn (a -> (b -> (c -> ... (... -> z) ...))) into ((a, (b, (c, ...))) -> z)
class Uncurry x y z where
  uncurry_ :: x -> y -> z

instance {-# OVERLAPPING #-} (Uncurry (b -> c) yb z, y ~ (a, yb)) => Uncurry (a -> b -> c) y z where
  uncurry_ f (a, yb) = uncurry_ (f a) yb

instance (a ~ y, b ~ z) => Uncurry (a -> b) y z where
  uncurry_ = id

一些例子：

testUncurry :: (Int, Int) -> Int
testUncurry = uncurry_ (+)

-- combined with arr
testUncurry2 :: (Int, (Int, (Int, Int))) :-> Int
testUncurry2 = arr (uncurry_ (\a b c d -> a + b + c + d))

完整要点：https://gist.github.com/Lysxia/c754f2fd6a514d66559b92469e373352

如何定义多元箭头？

How to define a polyvariadic arrow?

haskell

arrows

关于 `arrowfy @r @b @z` 语法的附注

如何定义多元箭头？

How to define a polyvariadic arrow?

haskell

arrows

关于 arrowfy @r @b @z 语法的附注

关于 `arrowfy @r @b @z` 语法的附注