val pigro per implementare liste pigri a Scala

Question

sto cercando di imparare ad usare il built-in pigrizia a Scala implementando la mia versione di liste pigri:

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 ++ ",..]" 
    } 
} 

Questo sembra funzionare e posso , per esempio, la mappa { _ + 2} alla lista infinita:

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

ho deciso di implementare alcune funzioni che io di solito uso come drop, take, ecc e sono stato in grado di attuarle tranne inits. La mia implementazione di inits è:

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

Il problema è che non funziona sulle liste infinite per qualche motivo. Non posso, ad esempio, scrivere:

> LazyList from 1 inits 

perché funziona per sempre. Il problema sembra essere fmap dopo il t.inits che, per qualche motivo, rompe la pigrizia (se rimuovo fmap è sbagliato ma pigro). Perché fmap applica rigore e, dato il mio tipo LazyList, come è possibile implementare inits in modo che funzioni su elenchi infiniti?

Answer 1

Entrambi fmap e inits rilasciano un elemento effettivo (non pigro) quando viene richiamato; sono entrambi uncons. Poiché si chiamano a vicenda, la catena non termina mai su un numero infinito LazyList.

In particolare, si noti che i rendimenti non uncons un => LazyList ma l'attuale LazyList, in modo che quando ti chiamano

Some((h,t)) 

che viene valutatat. Se la valutazione di t chiama un uncons, anche questo valuterà e si andrà alle corse di overflow dello stack. È difficile da notare qui perché è una doppia ricorsione.

È necessario fare uno di loro peel zero copie. Un modo per farlo è quello di fare il secondo argomento della uncons tupla pigro (in modo esplicito, rendendolo un Function0 invece):

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 ++ ",..]" 
    } 
} 

Allora la vostra applicazione funziona:

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

potrebbe essere più bello avere un uncons interno che ha fatto questo e un uncons rivolto verso l'esterno che applica la coda per te.