Geek Answers Handbook

Lazy val for implementing lazy lists in Scala

I am trying to learn how to use the built-in laziness in Scala by implementing my own version of lazy lists:

object LazyList { def empty[A] : LazyList[A] = new LazyList[A] { lazy val uncons = None } def cons[A](h : => A, t : => LazyList[A]) : LazyList[A] = new LazyList[A] { lazy val uncons = Some( (h,t) ) } def from(s : Int) : LazyList[Int] = new LazyList[Int] { lazy val uncons = Some( (s,from(s + 1)) ) } } trait LazyList[A] { import LazyList._ def uncons : Option[(A,LazyList[A])] def fmap[B](f : A => B) : LazyList[B] = uncons match { case None => empty case Some( (h,t) ) => cons(f(h),t.fmap(f)) } def take(i : Int) : LazyList[A] = uncons match { case None => empty case Some( (h,t) ) => if (i <= 0) empty else cons(h,t.take(i - 1)) } override def toString : String = uncons match { case None => "[]" case Some( (h,t) ) => "[" ++ h.toString ++ ",..]" } }

This works, and I can, for example, map { _ + 2} to an infinite list:

 > LazyList from 1 fmap { _ + 2 } res1: LazyList[Int] = [2,..]

I decided to implement some functions that I usually use as drop , take , etc., and I was able to implement them, except inits . My inits implementation:

  def inits : LazyList[LazyList[A]] = uncons match { case None => empty case Some( (h,t) ) => cons(empty,t.inits.fmap(cons(h,_))) }

The problem is that for some reason it does not work on endless lists. I cannot, for example, write:

  > LazyList from 1 inits

because it works forever. It seems that after t.inits problem is fmap , which for some reason breaks laziness (if I delete fmap , this is wrong, but lazy). Why fmap provide strictness and, given my LazyList type, how can I implement inits so that it works in infinite lists?

+6
source share
1 answer

Both fmap and inits clear one valid (non-default) element on invocation; they are both uncons . As they call each other, the chain never ends on an infinite LazyList .

In particular, note that uncons returns not => LazyList , but the actual LazyList , so when you call

 Some( (h,t) )

which values t . If the evaluation of t causes uncons , it will also be evaluated, and you go on to stack overflow. It is simply hard to notice here because it is double recursion.

You need to make one of them clear zero copies. One way to do this is to make the second tuple uncons argument lazy (explicitly by making Function0 instead):

 object LazyList { def empty[A]: LazyList[A] = new LazyList[A] { lazy val uncons = None } def cons[A](h: => A, t: => LazyList[A]) : LazyList[A] = new LazyList[A] { lazy val uncons = Some( (h,() => t) ) } def from(s: Int): LazyList[Int] = new LazyList[Int] { lazy val uncons = Some( (s,() => from(s + 1)) ) } } trait LazyList[A] { import LazyList._ def uncons: Option[(A,() => LazyList[A])] def fmap[B](f: A => B): LazyList[B] = uncons match { case None => empty case Some( (h,t) ) => cons(f(h),t().fmap(f)) } def take(i: Int): LazyList[A] = uncons match { case None => empty case Some( (h,t) ) => if (i <= 0) empty else cons(h,t().take(i - 1)) } override def toString: String = uncons match { case None => "[]" case Some( (h,t) ) => "[" ++ h.toString ++ ",..]" } }

Then your implementation is executed:

  def inits: LazyList[LazyList[A]] = uncons match { case None => empty case Some( (h,t) ) => cons(empty,t().inits.fmap(cons(h,_))) }

Perhaps it would be better to have the internal non-cones that did this, and the outward-looking villains who apply the tail to you.

+8
source

More articles:


All Articles