Generic Programming (6) - Data Structures - List Basics
List is one of the most common generalized data structures, relatively intuitive, and has a good demonstration base. A List is like a tube that can be loaded with a long bar of any type of thing. If you need to work on the contents of the tube, you must go one by one in linear order within the tube, which is consistent with the style of generic programming. As with other generic data structures, the design of a List starts by considering the two states of the List: empty or not empty types. These two types can be represented by case classes:
1 trait List[+A] {}
2 case class Cons[+A](head: A, tail: List[A]) extends List[A]
3 case object Nil extends List[Nothing]The above is a List that can be loaded with elements of type A, which is a Polymorphic Type. +A means that List is covariant, meaning that if apple is a subtype of fruit then List[apple] is a subclass of List[fruit]. Nil inherits from List[Nothing],Nothing is a subclass of all types. Combined with the covariance property, Nil can be considered as List[Int],List[String]...
An alternative implementation of List.
1 trait List[+A] {
2 def node: Option[(A, List[A])]
3 def isEmpty = node.isEmpty
4 }
5 object List {
6 def empty[A] = new List[A] { def node = None}
7 def cons[A](head: A, tail: List[A]) = new List[A] { def node = Some((head, tail))}
8 }The above code has two methods empty,cons to implement the two states of List.
We still use the first implementation for the following demonstration about List data operations. The second approach is left to Stream's specific implementation demonstration to illustrate.
Let's start with a List free builder: you can build a List in the form List(1,2,3):
1 object List {
2 def apply[A](as: A*): List[A] = {
3 if (as.isEmpty) Nil
4 else Cons(as.head,apply(as.tail:_*))
5 }
6 }Description: A recursive algorithm is used to handle a variable number of input parameters. The incoming argument to apply as is an array Array[A], and we use the methods of the Scala standard collection library Array:as.head, as.tail. The demonstration is as follows.
1 scala> Array(1,2,3).head 2 res11: Int = 1 3 4 scala> Array(1,2,3).tail 5 res12: Array[Int] = Array(2, 3)
Demonstrating the composition of a List with the addition of the apply method.
1 val li = List(1,2,3) //> li : ch3.list.List[Int] = Cons(1,Cons(2,Cons(3,Nil)))
2 val ls = List("one","two","three") //> ls : ch3.list.List[String] = Cons(one,Cons(two,Cons(three,Nil)))It is much more succinctly written in contrast to the way
1 val lInt = Cons(1,Cons(2,Cons(3,Nil))) //> lInt : ch3.list.Cons[Int] = Cons(1,Cons(2,Cons(3,Nil)))
Let's try one more operation: calculate the sum of all elements in List[Int], still written in pattern matching and recursive way:.
1 trait List[+A] {
2 def sum: Int = this match {
3 case Nil => 0
4 case Cons(h: Int,t: List[Int]) => h + t.sum
5 }
6 }We can put the implementation of sum into the trait affirmation with the following succinct expression.
1 List(1,2,3) sum //> res0: Int = 6
Try playing with the polymorphic function sum again:
1 def sum[B >: A](z: B)(f: (B,B) => B): B = this match {
2 case Nil => z
3 case Cons(h,t) => f(h, t.sum(z)(f))
4 }Now you can try List[Int] and List[String] separately:
1 List(1,2,3).sum(0){_ + _} //> res0: Int = 6
2 List("hello",",","World","!").sum(""){_ + _} //> res1: String = hello,World!The following are some functions that are commonly used by List.
1 trait List[+A] {
2
3 def head: A = this match {
4 case Nil => sys.error("Empty List!")
5 case Cons(h,t) => h
6 }
7 def tail: List[A] = this match {
8 case Nil => sys.error("Empty List!")
9 case Cons(h,t) => t
10 }
11 def take(n: Int): List[A] = n match {
12 case k if(k<0) => sys.error("index < 0 !")
13 case 0 => Nil
14 case _ => this match {
15 case Nil => Nil
16 case Cons(h,t) => Cons(h,t.take(n-1))
17 }
18 }
19 def takeWhile(f: A => Boolean): List[A] = this match {
20 case Nil => Nil
21 case Cons(h,t) => if(f(h)) Cons(h,t.takeWhile(f)) else Nil
22 }
23 def drop(n: Int): List[A] = n match {
24 case k if(k<0) => sys.error("index < 0 !")
25 case 0 => this
26 case _ => this match {
27 case Nil => Nil
28 case Cons(h,t) => t.drop(n-1)
29 }
30 }
31 def dropWhile(f: A => Boolean): List[A] = this match {
32 case Nil => Nil
33 case Cons(h,t) => if (f(h)) t.dropWhile(f) else this
34 }
35 }Look at these functions above; aren't they all relatively similar? That's because it's all a generalized style of programming. It is mainly implemented with pattern matching and recursive algorithms. The following is a demonstration of its use.
1 List(1,2,3).head //> res0: Int = 1
2 List(1,2,3).tail //> res1: ch3.list.List[Int] = Cons(2,Cons(3,Nil))
3 List(1,2,3).take(2) //> res2: ch3.list.List[Int] = Cons(1,Cons(2,Nil))
4 List(1,2,3).takeWhile(x => x < 3) //> res3: ch3.list.List[Int] = Cons(1,Cons(2,Nil))
5 List(1,2,3) takeWhile {_ < 3} //> res4: ch3.list.List[Int] = Cons(1,Cons(2,Nil))
6 List(1,2,3).drop(2) //> res5: ch3.list.List[Int] = Cons(3,Nil)
7 List(1,2,3).dropWhile(x => x < 3) //> res6: ch3.list.List[Int] = Cons(3,Nil)
8 List(1,2,3) dropWhile {_ < 3} //> res7: ch3.list.List[Int] = Cons(3,Nil)Try spelling a List after another List:.
1 def ++[B >: A](a: List[B]): List[B] = this match {
2 case Nil => a
3 case Cons(h,t) => Cons(h,t.++(a))
4 }1 ist(1,2) ++ List(3,4) //> res8: ch3.list.List[Int] = Cons(1,Cons(2,Cons(3,Cons(4,Nil))))
Just wanted to try out a concise expression of Scala.
Oh, I left out two.
1 def init: List[A] = this match {
2 case Cons(_,Nil) => Nil
3 case Cons(h,t) => Cons(h,t.init)
4 }
5 def length: Int = this match {
6 case Nil => 0
7 case Cons(h,t) => 1 + t.length
8 }1 List(1,2,3).init //> res9: ch3.list.List[Int] = Cons(1,Cons(2,Nil)) 2 List(1,2,3).length //> res10: Int = 3
A few functions common to generic data structures are implemented below.
1 def map[B](f: A => B): List[B] = this match {
2 case Nil => Nil
3 case Cons(h,t) => Cons(f(h),( t map f))
4 }
5 def flatMap[B]( f: A => List[B]): List[B] = this match {
6 case Nil => Nil
7 case Cons(h,t) => f(h) ++ ( t flatMap f )
8 }
9 def filter(f: A => Boolean): List[A] = this match {
10 case Nil => Nil
11 case Cons(h,t) => if (f(h)) Cons(h,t.filter(f)) else t.filter(f)
12 }1 List(1,2,3) map {_ + 10} //> res13: ch3.list.List[Int] = Cons(11,Cons(12,Cons(13,Nil)))
2 List(1,2,3) flatMap {x => List(x+10)} //> res14: ch3.list.List[Int] = Cons(11,Cons(12,Cons(13,Nil)))
3 List(1,2,3) filter {_ != 2} //> res15: ch3.list.List[Int] = Cons(1,Cons(3,Nil))There are several implementations of these functions, enabling Scala for-comprehension of the supported data structures. The rationale and significance of these functions in generic programming are described in detail later in the topics Functor, Applicative, and Monad.
Recommended>>
1、Netflix headline party makes Apple lie Apple employees have permission to see user privacy or not
2、Computer networks and information security above
3、When the blockchain is in close proximity to
4、8Pythons variable types
5、With the average monthly mobile phone traffic of users nationwide approaching 2G when will truly unlimited traffic be realized