Idris 中依赖类型函数自动检测域

Question

Idris 语言教程有简单易懂的示例 依赖类型 ： http://docs.idris-lang.org/en/latest/tutorial/typesfuns.html#first-class-types

代码如下：

isSingleton : Bool -> Type
isSingleton True = Int
isSingleton False = List Int

mkSingle : (x : Bool) -> isSingleton x
mkSingle True = 0
mkSingle False = []

sum : (single : Bool) -> isSingleton single -> Int
sum True x = x
sum False [] = 0
sum False (x :: xs) = x + sum False xs

我决定花更多时间在这个例子上。在 sum 函数中困扰我的是我需要明确地将 single : Bool 值传递给函数。我不想这样做，我希望编译器猜测这个布尔值应该是什么。因此，我只将 Int 或 List Int 传递给 sum 函数，布尔值和参数类型之间应该是一对一的对应关系（如果我传递其他类型，则不能类型检查）。

当然，我明白，这在一般情况下是不可能的。这样的编译器技巧要求我的函数 isSingleton（或任何其他类似函数）是 injective。但是对于这种情况，在我看来应该是可能的...

所以我开始下一个实现：我只是隐含了 single 参数。

sum : {single : Bool} -> isSingleton single -> Int
sum {single = True} x = x
sum {single = False} [] = 0
sum {single = False} (x :: xs) = x + sum' {single = False} xs

嗯，这并没有真正解决我的问题，因为我仍然需要在接下来的方式中调用这个函数：

sum {single=True} 1

但我在教程中读到了有关 auto 关键字的内容。虽然我不太明白 auto 的作用（因为我没有找到它的描述），但我决定稍微修补一下我的函数：

sum' : {auto single : Bool} -> isSingleton single -> Int
sum' {single = True} x = x
sum' {single = False} [] = 0
sum' {single = False} (x :: xs) = x + sum' {single = False} xs

它适用于列表！

*DepFun> :t sum'
sum' : {auto single : Bool} -> isSingleton single -> Int
*DepFun> sum' [1,2,3]
6 : Int

但不适用于单值:(

*DepFun> sum' 3
When checking an application of function Main.sum':
        List Int is not a numeric type

有人可以解释一下目前在这种单射函数用法中是否真的可以实现我的目标？我看了这个关于证明某物是单射的短片： https://www.youtube.com/watch?v=7Ml8u7DFgAk

但我不明白如何在我的示例中使用此类证明。如果这不可能，那么编写此类函数的最佳方法是什么？

Answer 1

auto关键字基本上告诉伊德里斯，"Find me any value of this type"。因此，除非该类型仅包含一个值，否则您很可能会得到错误的答案。 Idris 看到 {auto x : Bool} 并用任何旧的 Bool 填充它，即 False。它不会使用其对后续参数的了解来帮助它进行选择 - 信息不会从右向左流动。

一个解决方法是使信息流向另一个方向。而不是像上面那样使用 Universe 样式的构造，而是编写一个接受任意类型的函数，并使用谓词将其细化为您想要的两个选项。这样 Idris 就可以查看前面参数的类型并选择 IsListOrInt 类型匹配的唯一值。

data IsListOrInt a where
    IsInt : IsListOrInt Int
    IsList : IsListOrInt (List Int)

sum : a -> {auto isListOrInt : IsListOrInt a} -> Int
sum x {IsInt} = x
sum [] {IsList} = 0
sum (x :: xs) {IsList} = x + sum xs

现在，在这种情况下，搜索 space 足够小（两个值 - True 和 False），Idris 可以以蛮力方式可行地探索每个选项，并且选择第一个导致程序通过类型检查器的算法，但当类型远大于两个或尝试推断多个值时，该算法无法很好地扩展。

将上例中信息流的从左到右的性质与常规非auto 大括号的行为进行比较，后者指示 Idris 在 双向中查找结果时尚使用统一。正如您所注意到的，这只有在所讨论的类型函数是单射的时候才能成功。您可以将输入构造为单独的索引数据类型，并允许 Idris 查看构造函数以使用统一查找 b。

data OneOrMany isOne where
    One : Int -> OneOrMany True
    Many : List Int -> OneOrMany False

sum : {b : Bool} -> OneOrMany b -> Int
sum (One x) = x
sum (Many []) = 0
sum (Many (x :: xs)) = x + sum (Many xs)

test = sum (One 3) + sum (Many [29, 43])

预测机器何时能或不能猜出你的意思是依赖类型编程的一项重要技能；随着经验的增加，你会发现自己会变得更好。

当然，在这种情况下，这一切都没有实际意义，因为列表已经具有一个或多个语义。在普通的旧列表上编写您的函数；然后如果你需要将它应用到单个值，你可以将它包装在一个单例列表中。

Idris 中依赖类型函数自动检测域

Automatic detection of domain for dependent type function in Idris

functional-programming

dependent-type

idris

injective-function