Stream的#::实现

本文来自fair-jm.iteye.com 转截请注明出处

 

前端时间买了本 FP in scala(电子版 可以paypal付 双币信用卡就可以) 粗粗地看 看到了Stream惰性求值那章就想自己写一写

按照这本书写了写

于是想了想scala类库中的scala.collection.immutable.Stream中的 #::操作是如何实现的呢:

 

	1 #:: {println(2);2} #:: {println("empty");scala.collection.immutable.Stream.empty[Int]}

#::是惰性求值的  不会对后面的结果求值 所以结果是 

 

 

res0: scala.collection.immutable.Stream[Int] = Stream(1, ?)

 并没有输出 2 和 empty

 

 

对于scala的中缀表达式 我们知道要实现中缀 那么这个中缀运算符一定是前面或者后面参数的一个方法 因为这个操作符是以 : 结尾的所以他就是Stream的一个方法 我按照这个思路自己先尝试了下:

 

package cp5

sealed abstract class Stream[+A] {
    def take(n: Int): Stream[A]
    def drop(n: Int): Stream[A]
    def map[B >: A](f: A => B): Stream[B]
    
    def foreach[A](f: A => Unit): Unit = this match {
        case Empty =>
        case c: Cons[A] =>
            f(c.head)
            c.tail.foreach(f)
    }
    
    def #::[B >: A](e:B):Stream[B] = Stream.cons(e, this)
}

case object Empty extends Stream[Nothing] {
    override def take(n: Int): Stream[Nothing] = Empty
    override def drop(n: Int): Stream[Nothing] = Empty
    override def map[B](f: Nothing => B) = Empty
}

case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A] {
    lazy val head = h()
    lazy val tail = t()
    override def take(n: Int): Stream[A] = {
        if (n == 1) Cons(h, () => Empty)
        else Cons(h, () => tail.take(n - 1))
    }
    override def drop(n: Int): Stream[A] = {
        if (n == 1) tail
        else tail.drop(n - 1)
    }
    override def map[B >: A](f: A => B): Stream[B] = {
        Stream.cons(f(head), tail.map(f))
    }
}

object Stream {
    def cons[A, B >: A](h: => B, t: => Stream[A]): Stream[B] = {
        Cons(() => h, () => t)
    }

    def apply[A](e: A*): Stream[A] = {
        if (e.isEmpty) {
            Empty
        } else {
            Stream.cons(e.head, apply(e.tail: _*))
        }
    }
}

object Main {
    def main(args: Array[String]): Unit = {
        val s = Stream(1, 2, 3, 4, 5, 6).map((i: Int) => i * 2)
        1 #:: {println(2);2} #:: {println(4);Stream(3)}
    }
}

 没有报错  

 

 但遗憾的是在运行的时候会打印出

 2

 3

没有达到后面参数的惰性求值

 

后来考虑了一下发现这样做是不对的...如果是Stream的方法的话就一定会对{println(3);Stream(3)}进行求值 得到Stream(3)(不然怎么调用他的方法)

将这个 #:: 写在Stream里肯定是不行的

但这样如何实现呢.... 考虑了一会儿想到不如直接看源码

果不其然 源码的实现 #::并不是Stream的方法:

 

object Stream extends SeqFactory[Stream] {
 ... ...
  /** A wrapper class that adds `#::` for cons and `#:::` for concat as operations
   *  to streams.
   */
  class ConsWrapper[A](tl: => Stream[A]) {
    def #::(hd: A): Stream[A] = cons(hd, tl)
    def #:::(prefix: Stream[A]): Stream[A] = prefix append tl
  }
... ...
}

 接下来的问题是 我们写的是Stream 他是怎么变为ConsWrapper的呢...

 

答案就很明显了 用隐式转换..

 

  implicit def consWrapper[A](stream: => Stream[A]): ConsWrapper[A] =
    new ConsWrapper[A](stream)

 

 

 

仿照写了下 如下:

 

package cp5

sealed abstract class Stream[+A] { ... }

case object Empty extends Stream[Nothing] {...}

case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A] {
    lazy val head = h()
    lazy val tail = t()
    override def take(n: Int): Stream[A] = {
        if (n == 1) Cons(h, () => Empty)
        else Cons(h, () => tail.take(n - 1))
    }
    ... ...
}

object Stream {
    def cons[A, B >: A](h: => B, t: => Stream[A]): Stream[B] = {
        Cons(() => h, () => t)
    }

    def apply[A](e: A*): Stream[A] = {
        if (e.isEmpty) {
            Empty
        } else {
            Stream.cons(e.head, apply(e.tail: _*))
        }
    }
    
  class ConsWrapper[A](tl: => Stream[A]) {
    def #::(hd: A): Stream[A] = cons(hd, tl)
  }
  
  implicit def convert[A](s: =>Stream[A]):ConsWrapper[A] = {
      new ConsWrapper(s)
  }
}

object Main {
    def main(args: Array[String]): Unit = {
        1 #:: {println(2);2} #:: {println(3);Stream(3)}
    }
}

 接下去就是运行 没有输出2 3 运行正常

 

 

 此外 可以在源码里发现还有个 #::类:

 

  /** An extractor that allows to pattern match streams with `#::`.
   */
  object #:: {
    def unapply[A](xs: Stream[A]): Option[(A, Stream[A])] =
      if (xs.isEmpty) None
      else Some((xs.head, xs.tail))
  }

关于这个在洪江大大的博客里有提及:

scala雾中风景(5): 中缀表达

 

这里可见scala支持call-by-name 惰性求值 以及 隐式转换 可以实现很多用java根本无法实现的功能 但其实现的方式可能会有点曲折

哎 觉得scala真的挺有趣的 但现在的工作用不上它 只能作为业余爱好略有可惜