Rank N Types

发表于 更新于 分类于

前几日在和朋友讨论一个 Rust 的编程问题。

https://play.rust-lang.org/?version
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#[cfg(test)]
mod tests {
    use super::*;
    use std::collections::HashMap;


    pub fn sort<T: Ord>(arr: &mut [T]) {
        // ...
    }

    pub fn sort2<T: Ord>(arr: &mut [T]) {
        // ...
    }

    fn functions<T: Ord>() -> HashMap<String, fn(&mut [T])> {
        let mut sorts = HashMap::new();
        
        // not working
        sorts.insert("sort".to_string(), sort);
        sorts.insert("insert".to_string(), sort2);
        
        // it's working 
        // sorts.insert("sort".to_string(), sort as fn(&mut [T]));
        // sorts.insert("insert".to_string(), sort2 as fn(&mut [T]) );

        return sorts;
    }
}

刚好遇见之前在 Java 不会遇见的 Rank N Types 问题，我们来掰扯一下。

泛型函数

我们声明一个 chooseString 函数，我们可以很简单的随机获得一个 String

1
2
3
4
5
6
7
String chooseString(String head, String tail) {
  if (Math.random() < 0.5) {
    return head;
  } else {
    return tail;
  }
}

因为不够通用，我们将其改为泛型函数

1
2
3
4
5
6
7
<T> T chooseValue(T head, T tail) {
  if (Math.random() < 0.5) {
    return head;
  } else {
    return tail;
  }
}

在编译完成之后，函数签名会变成 com.example.demo.Function.chooseValue(Object, Object) : Object 我们此时的 T 类型早已被擦拭。在 Java 中函数还不是一等公民尚且没有更多的问题，我们来用 Rust 模拟下

1
2
3
4
5
6
7
fn main() {
    let mut func = chooseValue;
}

fn chooseValue<T>(one: T, two: T) -> T {
    return one
}

我们将 chooseValue 作为一个变量 func，此时编译器会报错

1
2
3
4
5
6
--> src/main.rs:2:24
  |
2 |     let mut func = chooseValue;
  |         ------------   ^^^^^^^^^^^ cannot infer type for type parameter `T` declared on the func `chooseValue`
  |         |
  |         consider giving `func` the explicit type `fn(T, T) -> T`, where the type parameter `T` is specified

因为对于类型语言来说，我们此时不知道这个函数的入参类型 (one two)，因此我们也不知道这个函数的真正的类型。由于 Rust 是一个静态的强类型语言
因此对于编译时期我们就需要获得这个类型，我们只能这样去操作。

1
2
3
4
5
6
7
fn main() {
    let mut func = chooseValue::<String>;
}

fn chooseValue<T>(one: T, two: T) -> T {
    return one
}

Higher-rank types

Higher-rank types 的目标就是让多态函数也可以变成一等公民。

Rank-1 polymorphism

我们申明一个函数 length

1
length :: [a] -> Int

将 a 原样返回，这个 a 也是一个类型，不过可以代指所有的类型。
因此我们可以在这里返回任意数组的长度。这其实是

1
length :: forall a. [a] -> Int

的一种隐性声明。

Rank-2 polymorphism

我们继续声明函数在 Haskell98 中

1
2
bar :: (a -> a) -> (Char, Bool) # 等价于 bar :: forall a. ((a -> a) -> (Char, Bool))
bar f = (f 'c', f True)

此时的声明式会编译错误，因为 f 的类型是多态的，可以接受 Char 也可以接受 Bool 并不满足 (forall a. a -> a) 的要求
而正确的处理姿势是 

1
2
foo :: (forall a. a -> a) -> (Char,Bool)
foo f = (f 'c', f True)

我们把这里的 bar 称之为 rank-1 type，foo 称为 rank-2 type，那么就好理解对于 rank-N type了，可以支持任意类型的即可。

参考