美文网首页
Essential Scala: DRY List

Essential Scala: DRY List

作者: 刘光聪 | 来源:发表于2016-07-05 21:12 被阅读170次

在函数式设计中,递归是一种重要的思维。本文通过List的实现为例,阐述Scala在设计具有「不变性」数据结构的思路和技巧。

递归的数据结构

sealed abstract class List[+A]

final case class ::[A](head: A, tail: List[A]) extends List[A]
final case object Nil extends List[Nothing]

递归的的算法

sealed abstract class List[+A] {
  ...
  
  def map[B](f: A => B): List[B] = this match {
    case Nil => Nil
    case h :: t => f(h) :: t.map(f)
  }

  def filter(f: A => Boolean): List[A] = this match {
    case Nil => Nil
    case h :: t => if(f(h)) h :: t.filter(f) else t.filter(f)
  }

  def foreach[U](f: A => U): Unit = this match {
    case Nil => ()
    case h :: t => { f(h); t.foreach(f) }
  }
  
  def forall(f: A => Boolean): Boolean = this match {
    case Nil => true
    case h :: t => f(h) && t.forall(f)
  }
  
  def exists(f: A => Boolean): Boolean = this match {
    case Nil => false
    case h :: t => f(h) || t.exists(f)
  }
}

最终类

不能在类定义的文件之外定义List的任何新的子类。List只有两个子类:

  • case class ::[A]
  • case object Nil

这使得List.map, filter, foreach等方法可以使用「模式匹配」的原因。

协变

List[+A]的类型参数是「协变」的。

  • Nothing是任何类的子类;
  • List[Nothing],或Nil也是List[A]的子类;

:结尾的方法

定义::Cons操作,其具有特殊的结合性;

结合性
sealed abstract class List[+A] {
  def ::[B >: A] (x: B): List[B] = new ::(x, this)
  ...
}

:结尾的方法,Scala具有特殊的结合性。

1 :: 2 :: 3 :: Nil      // List(1, 2, 3)

等价于:

Nil.::(3).::(2).::(1)  // List(1, 2, 3)
逆变点

参数xList方法::中定义本来是一个「逆变点」,这与List[+A]的协变相矛盾,为此通过提供类型「下界」,并保证其「不变性」,使得这两个现象得以和谐。

def ::[B >: A] (x: B): List[B] = new ::(x, this)

相关文章

  • Essential Scala: DRY List

    在函数式设计中,递归是一种重要的思维。本文通过List的实现为例,阐述Scala在设计具有「不变性」数据结构的思路...

  • scala 2.13.1 数组 和Java List互转

    Scala数组 转 Java List List 转 Scala数组

  • Essential Scala: Literals

    Scala对象系统 总体上,Scala对象系统可分为两类: 引用类型 值类型 引用类型 AnyRef的子类 使用n...

  • Essential Scala: Bounds

    上界 隐式参数 可以提供「隐式参数」,改善smaller的设计。 当T为Int 编译器实际调用: 其中Orderi...

  • essential scala: 伴生对象

    essential scala: 伴生对象 有时候我们想创建属于类的方法,在java中使用static关键字. 在...

  • Essential Scala: Import Specfica

    Scala是一门很自由的程序设计语言,程序员可以根据具体场景,选择最合适的武器来解决所面对的问题。例如,相对于Ja...

  • Essential Scala: Ice Breaker

    Scala是一门结合OO, FP特性的混血儿,支持多种范式的程序设计语言。本文通过一个简单的例子,开启Scala的...

  • Essential Scala:Parameter Type &

    参数化类型 Reader 定义泛型的Reader[+T],并赋予协变的能力。 StringReader FileR...

  • Essential Scala: Loan Pattern

    资源自动回收是计算机工程实践中一项重要的实现模式,例如: C++: RAII技术 Java7以后:try-with...

  • Essential Scala: Type Constraint

    Scala提供了3个类型约束的类: T =:= U: T是否等于U T <:< U: T是否为U的子类型 T <%...

网友评论

      本文标题:Essential Scala: DRY List

      本文链接:https://www.haomeiwen.com/subject/jqzhjttx.html