一般的类型和一般的方法 (Generic Types and Methods) 齐琦

Size: px

Start display at page:

Download "一般的类型和一般的方法 (Generic Types and Methods) 齐琦"

谱共綦柯
5 years ago
Views:

1 今天的内容 n 一般的类型和一般的方法 n 列表集合 (Lists)

2 一般的类型和一般的方法 (Generic Types and Methods) 齐琦

3 为什么需要一般类型? 如何再定义一个字符串堆栈?

4 一般类型 (generic types) 含有类型参数 n 类型参数名字任意, 在 [ ] 中如何使用

5 一般的方法 (generic methods) 类型参数值参数 n 有类型参数的方法 n 多形的 (polymorphic = having many forms ) n 局部类型推理, 在使用时可省略类型参数 n isprefix(s1,s2)

6 类型参数界限 : 为什么需要? n 加入类型参数 [A] n A 有定义 > 或 < 方法吗?

7 类型参数界限 n 输入类型需要限制 n Trait Ordered[A]{ } n 本身类的值可相互比较 n 规定输入类型的值必须可比较 ( 它是 Ordered 的子类型 )

8 类型参数界限, 继续 n 使用之前的类定义值

9 类型参数界限,view bounds n 如果还不是 Ordered 的子类? n Int, Double, String, 从 Java 继承来的 n View bounds, <% n 隐式转换存在就行

10 一般类型的变化标识 (generic types variance) n 问题 : 如何避免程序中类型不匹配? 潜在的问题? Java: 在 #3 行, 运行时检查 (run-time check) 类型 Scala: 在 #2 行, 静态时编译检查 ;Array 在 Scala 里不允许变体子类 (non-variant subtyping)

11 同变 ( 子类化 ) (Co-variant subtyping) n If T 是 S 的子类, then Stack[T] 是 Stack[S] 的子类 n Scala 里的一般类型 (generic types) 缺省是无变体子类化 (nonvariant subtyping) n 强制同变的符号 : + n Class Stack[+A] n 纯函数世界, 所有类型都可能成为同变的, 但是当引入可变数据时, 情况就不一样了

12 反变子类化 (contra-variant subtyping) n 表示 :Class Stack[-A] n 如果 T 是 S 的子类, 那么 Stack[S] 是 Stack[T] 的子类

13 问题 : 如何验证变化标识的合理性? n 如果 array 被定义成同变的 (co-variant), 怎么及时检测出这个潜在的问题? n Scala 采用了一种保守的估计方法 n 同变类型参数只应出现在同变的位置上 n 同变的位置有 : n 类中值的类型 n 类中方法的返回类型 n 其他同变类型的类型输入参数 n 非同变位置有 : n 类中正式方法的参数类型

14 问题 : 如何验证变化标识的合理性? Update 改变状态, 影响了同变子类化的合理性 Stacks 是纯函数数据类型 Push 没有改变状态, 但仍会被挑错, 怎么办?

15 一般类型参数的 : 底界 n T >: S, 类型参数 T 只能是类型 S 的父类 (supertypes) n T >: S <: U n Push in Stack,A 不出现在 push 的参数类型位置 ; 一个方法的类型参数的底界 ( 这个位置是同变 (co-variant) 位置 ) n 不仅解决了技术问题, 也通用化了 push 的定义 n Push 是一个多态方法 (polymorphic method) n What if push[b >: A] changed to [B<:A]? What would happen? n Can I push an Int value onto a String Stack?

16 EmptyStack 的定义 n 对象不能有类型参数 n Nothing 是所有其他类型的子类 ;For co-variant stacks, Stack[Nothing] is a subtype of Stack[T]

17 Stack 的完整定义

18 一般类型实例 generic class: tuples and functions

19 Tuples 类型参数可忽略 n Tuple2: 含有两个值 ; Tuplen(): n 个值 n 可直接用 (x/y, x % y)

20 + Tuples

21 函数 (Functions) n Scala,a functional language; functions are first-class values n Also a object-oriented language; every value is an object. n Functions are objects. n (T1,, Tn) => S 缩写 Functionn[T1,, Tn, S] n f(x) shorthand for f.apply(x)

22 函数 (Functions) n 反变类型参数的应用 (contra-variant type parameter) n Function subtyping is contra-variant in its argument type whereas co-variant in its result type. n S => T n S => T

23 函数的对象本质通常的函数使用实体化一个抽象类? 行吗? 面向对象代码 ; New Function1 构建了匿名类, 实现了 apply 方法 ; Function1 是抽象类使用命名的类扩展 Function1

24 类型参数的子类变化控制的本质用意 n 子类值可以被赋给父类 ( 变量 ); 反之不行

25 列表集合 (Lists) 海南大学齐琦

26 List 简介 n 和数组 (C 或 Java 里的 Array) 的区别 n 不可变的 (immutable); 元素不能被赋值改变 n 递归结构 ; 数组是平的 n 支持更丰富的操作

27 使用列表 (Lists) n 元素都是同类型的 ;List[T] n 构造组件 n Nil 空表 n :: ( cons ) 中间操作符, 扩展表达 n x :: xs 第一个元素是 x n 向右结合

28 Lists 基本操作 n head n tail n isempty n Head 和 tail 方法只为非空链表定义 ; 空的调用会出错 (exception)

29 使用举例 : 插入排序 n 如何实现 insert 函数?

30 列表模式 (List pattern) n :: 被定义为一个实例类 (case class), 可以用模式匹配来分解链表

31 List 类定义介绍 n 不是嵌入式类型 ; 抽象类, 和子类 ::, Nil. n Co-variant 类型参数 A n List[S] <: List[T] for all types S and T such that S <: T

32 分解列表 (Decomposing Lists)

33 List 方法 n 长度方法 n 如何实现尾递归形式 n Last element; all elements except the last n Have to traverse entire list

34 List 方法, 继续 n Return a prefix, or a suffix, or both 返回第 n 个元素 ;indices start at 0. Xs.apply(3) or xs(3); 好像函数子表 xs_m,, xs_n-1, xs.drop(m).take(n-m)

35 拉链 (Zipping lists) n Longer list will be truncated. n Zip, a polymorphic method

36 在列表头添加元素 n ::, implemented as a method in class List n 向右结合

37 串联列表 (Concatenating lists) n :::, 右结合, 右手操作元素的一个方法

38 反转列表 n Reverse 方法 n 这个实现效率低, 为什么? n 时间复杂度

39 + Merge sort

40 List 的高阶方法

41 List 上的计算模式总结 n 计算模式 n 对每个元素进行转换 n 选出满足某个条件的所有元素 n 对元素进行某种方式上的组合 n 通过高阶函数来实现以上模式 n List 的方法

42 Mapping ( 映射 ) n 变换每个元素

43 For each 方法 n 对每个元素应用一个函数, 但不返回一个列表结果 n 为了副作用 (side effect) 而设 n In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world. For example, a function might modify a global variable or static variable, modify one of its arguments, raise an exception, write data to a display or file, read data, or call other sideeffecting functions.

44 Filtering( 过滤列表 )

+ 演示代码已发布到 Github n

+ 演示代码已发布到 Github n 演示代码已发布到 Github n https://github.com/qiqi789/myscalacourse 今天的内容 n Scala 基础 ( 继续 ) n Scala 类和对象 n Scala 实例类和模式匹配 n 一般的类型和一般的方法 Scala 基础齐琦海南大学 Scala interpreter( 解释器 ) Sbt console (Scala 命令行解释器 ) 定义变量,