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
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

已推荐到看一看 和朋友分享想法
最多200字，当前共 发送

已发送

确定
分享你的想法...
取消

确定
最多200字，当前共

发送中