Notes on Functional programming 12

`Stream`

To find the second prime between 1000 and 10000, write:

((1000 to 10000) filter isPrime)(1)
Copy the code

It’s not very good performance, you only need a second prime, but you find all the primes from 1000 to 10000.

It can be improved with streams, which are similar to lists, but are evaluated only when needed.

A Stream is defined by a constant stream.empty and a constructor stream.cons:

val xs = Stream.cons(1.Stream.cons(2.Stream.empty))
// Steam can also be used as factory
Stream(1.2.3)
// toStream turns a collection into a stream
(1 to 1000).toStream    // > res0: Stream[Int] = Stream(1, ?)
Copy the code

Consider a function similar to (lo until hi).tostream:

def streamRange(lo: Int, hi: Int) :Stream[Int] =
    if(lo >= hi) Stream.empty
    else Stream.cons(lo, streamRange(lo + 1, hi))
Copy the code

Compare to its List version:

def listRange(lo: Int, hi: Int) :List[Int] =
    if (lo > hi) Nil
    else lo :: listRange(lo + 1, hi)
Copy the code

Their differences are mainly in the way of evaluation:

listRange(start, end)Generates a file containing data fromendtostartList of elements
streamRange(start, end)Will generate astartThe stream that is the header element
The remaining elements are evaluated only when needed, which means called on the streamtailwhen

The stream supports most of the operations on the list. The previous code to find prime numbers could be written as follows:

((1000 to 10000).toStream filter isPrime)(1)    // Only the first two primes are evaluated
Copy the code

The biggest difference between stream and list operations is the concatenation, x :: xs generates lists, while x #:: xs generates streams. #:: can also be used in patterns.

This is the trait of flow:

trait Stream[+A] extends Seq[A] {
    def isEmpty: Boolean
    def head: A
    def tail: Stream[A]}Copy the code

Here’s a simple implementation of a stream:

object Stream {
    def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] {
        def isEmpty = false
        def head = hd
        def tail = tl
    }
    val empty = new Stream[Nothing] {
        def isEmpty = true
        def head = throw new NoSuchElementException("empty.head")
        def tail = throw new NoSuchElementException("empty.tail")}}Copy the code

You can see that the call-by-name parameter => is used, so it will not be evaluated immediately.

This is the implementation of the filter method:

class Stream[+T] {...def filter(p: T= >Boolean) :Stream[T] =
    if (isEmpty) this
    else if(p) (head) cons (head, tail. The filter ℗)elseTail. The filter ℗}Copy the code

Lazy Evaluation

The previous implementation had a serious performance problem in that if the tail method of a stream was called more than once, the corresponding stream would be evaluated more than once. This problem can be solved by saving the computed value, a solution that is reliable because in purely functional programming the value of an expression is constant whenever it is evaluated.

This method is called lazy evaluation, as opposed to by-name evaluation (which is reevaluated every time) and direct (strict) evaluation (common arguments and val definitions).

Haskell uses lazy evaluation by default, Scala uses direct evaluation by default, but lazy val is also allowed to apply lazy evaluation:

lazy val x = expr
Copy the code

Exercise: What is the result of the following code?

def expr = {
    val x = { print("x"); 1 }
    lazy val y = { print("y"); 2 }
    def z = { print("z"); 3 }
    z + y + x + z + y + x
}
expr
Copy the code

The answer is xzyz.

The previous Stream implementation can be changed to lazy evaluation:

def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] {
    def head = hd
    lazy valTail = tl... }Copy the code

Infinite flow

For example, all integers starting with a given integer:

def from(n: Int) :Stream[Int] = n #:: from(n+1)
val nats = from(0)
Copy the code

Example: The Sieve of Eratosthenes for prime numbers.

object primes {
  def from(n: Int) :Stream[Int] = n #:: from(n+1)        // > from: (n: Int)Stream[Int]
  def sieve(s: Stream[Int) :Stream[Int] = s.head #:: sieve(s.tail filter (_ % s.head ! =0))    // > sieve: (s: Stream[Int])Stream[Int]
  val primes = sieve(from(2))                            // > primes: Stream[Int] = Stream(2, ?)
  (primes take 10).toList                                // > res0: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
}
Copy the code

Recalling the SQRT function in Newton’s square root, we can reconstruct it with Stream:

def sqrtStream(x: Double) :Stream[Double] = {
    def improve(guess: Double) = (guess + x / guess) / 2
    lazy val guesses: Stream[Double] = 1#:: (map improve) Guess}... sqrtStream(4) filter (isGoodEnough(_, 4))
Copy the code

General practice: pour water problem

There is a sink and a number of cups without scale only know the capacity, how to operate to pour out the amount of water needed?

A simple plan:

The Glass Glass:Int
State of the State:Vector[Int]
Operate the Moves:
- emptyEmpty(glass)
- Filled withFill(glass)
- Pour from cup to cupPour(from, to)

Code:

class Pouring(capacity: Vector[Int]) {
  // States
  type State = Vector[Int]
  val initialState = capacity map (x => 0)
  // Moves
  trait Move {
    def change(state: State) :State
  }
  case class Empty(glass: Int) extends Move {
    def change(state: State) = state updated(glass, 0)}case class Fill(glass: Int) extends Move {
    def change(state: State) = state updated(glass, capacity(glass))
  }
  case class Pour(from: Int, to: Int) extends Move {
    def change(state: State) = {
      val amount = state(from) min (capacity(to) - state(to))
      state updated(from, state(from) - amount) updated(to, state(to) + amount)
    }
  }
  val glasses = 0 until capacity.length
  val moves =
    (for (g <- glasses) yield Empty(g)) ++
      (for (g <- glasses) yield Fill(g)) ++
      (for (from <- glasses; to <- glasses iffrom ! = to)yield Pour(from, to))
  // Paths
  class Path(history: List[Move], val endState: State) {
    def extend(move: Move) = new Path(move :: history, move change endState)
    override def toString = (history.reverse mkString "") + "--> " + endState
  }
  val initialPath = new Path(Nil, initialState)
  def from(paths: Set[Path], explored: Set[State) :Stream[Set[Path]] =
    if(paths.isEmpty) Stream.empty
    else {
      val more = for {
        path <- paths
        next <- moves map path.extend
        if! (explored contains next.endState) }yield next
      paths #:: from(more, explored ++ (more map (_.endState)))
    }
  val pathSets = from(Set(initialPath), Set(initialState))
  def solutions(target: Int) :Stream[Path] =
    for {
      pathSet <- pathSets
      path <- pathSet
      if path.endState contains target
    } yield path
}
object test {
  val problem = new Pouring(Vector(4.9.19))    // > problem: Pouring = Pouring@1e86486b
  problem.moves                                  // > res0: scala.collection.immutable.IndexedSeq[Product with Serializable with problem.Move] = Vector(Empty(0), Empty(1), The Empty (2), the Fill (0), the Fill (1), the Fill (2), Pour (0, 1), Pour (0, 2), Pour (1, 0), Pour (1, 2), Pour (2, 0), Pour (2, 1))
  problem.solutions(17)                          // > res1: Stream[problem.Path] = Stream(Fill(0) Pour(0,2) Fill(0) Fill(1) Pour(0,2) Pour(1,2)--> Vector(0, 0, 17),?
}
Copy the code

Note when code gets longer:

Name it as much as possible
Put operations in the natural scope
Keep optimizability

More resources

Please refer directly to Functional Programming Principles in Scala.

– the –

Stream

Lazy Evaluation

Infinite flow

General practice: pour water problem

More resources

Related Posts

The road ahead for Service Mesh is long enough to expect

Not all Spring Boot exceptions can be handled uniformly

CentOS Installs the Nacos server

`Stream`