Come inserire elementi di 2 elenchi in scala

Question

Vorrei combinare due elenchi di lunghezza arbitraria in modo che gli elementi della seconda lista vengano inseriti dopo ogni n-esimo elemento nella prima lista. Se la prima lunghezza dell'elenco è inferiore a n, non viene generato alcun risultato.

Quindi, avendo

val a = List(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15) 
val b = List(101,102,103) 
val n = 3 

voglio l'elenco risultante a guardare come questo:

List(1,2,3,101,4,5,6,102,7,8,9,103,10,11,12,13,14,15) 

Ho questo lavoro utilizzando un foldLeft su a, ma mi chiedo come la stessa logica potrebbe essere realizzato usando Scalaz?

Grazie per le risposte di tutti. Sono stati tutti utili per me!

Answer 1

incontrare il mio amico apomorphism

def apo[A, B](v: B)(f: B => Option[(A, Either[B, List[A]])]): List[A] = f(v) match { 
    case None => Nil 
    case Some((a, Left(b))) => a :: apo(b)(f) 
    case Some((a, Right(as))) => a :: as 
} 

Il tuo metodo interleave può essere implementato come questo

def interleave[A](period: Int, substitutes: List[A], elems: List[A]): List[A] = 
    apo((period, substitutes, elems)){ 
    case (_, _, Nil)  => None 
    case (_, Nil, v :: vs) => Some((v, Right(vs))) 
    case (0, x :: xs, vs) => Some((x, Left((period, xs, vs)))) 
    case (n, xs, v :: vs) => Some((v, Left((n - 1, xs, vs)))) 
    } 

Questo dà:

scala> interleave(3, b, a) 
res1: List[Int] = List(1, 2, 3, 101, 4, 5, 6, 102, 7, 8, 9, 103 , 10, 11 , 12, 13, 14, 15) 

Il punto positivo è il calcolo termina quando una o b sono nulle differenza foldLeft. La cattiva notizia è interleave non è più ricorsivo di coda

Answer 2

Che dire:

def interleave[A](xs: Seq[A], ys: Seq[A], n: Int): Seq[A] = { 
    val iter = xs grouped n 
    val coll = iter zip ys.iterator flatMap { case (xs, y) => if (xs.size == n) xs :+ y else xs } 
    (coll ++ iter.flatten).toIndexedSeq 
} 

scala> interleave(a, b, n) 
res34: Seq[Int] = Vector(1, 2, 3, 101, 4, 5, 6, 102, 7, 8, 9, 103, 10, 11, 12, 13, 14, 15) 

scala> interleave(1 to 2, b, n) 
res35: Seq[Int] = Vector(1, 2) 

scala> interleave(1 to 6, b, n) 
res36: Seq[Int] = Vector(1, 2, 3, 101, 4, 5, 6, 102) 

scala> interleave(1 to 7 b, n) 
res37: Seq[Int] = Vector(1, 2, 3, 101, 4, 5, 6, 102, 7) 

scala> interleave(1 to 7, Nil, n) 
res38: Seq[Int] = Vector(1, 2, 3, 4, 5, 6, 7) 

scala> interleave(1 to 7, Nil, -3) 
java.lang.IllegalArgumentException: requirement failed: size=-3 and step=-3, but both must be positive 

È breve, ma non è la soluzione più efficiente. Ad esempio, se si chiama Elenchi, le operazioni di aggiunta (:+ e ++) sono costose (O(n)).

EDIT: Mi dispiace. Ora noto che vuoi avere una soluzione con Scalaz. Tuttavia la risposta potrebbe essere utile quindi non la cancellerò.

Answer 3

ne dite di questo:

def process[A](xs: List[A], ys: List[A], n: Int): List[A] = 
    if(xs.size <= n || ys.size == 0) xs 
    else xs.take(n):::ys.head::process(xs.drop(n),ys.tail,n) 

---

scala> process(a,b,n) 
res8: List[Int] = List(1, 2, 3, 101, 4, 5, 6, 102, 7, 8, 9, 103, 10, 11, 12, 13, 14, 15) 

scala> val a = List(1,2,3,4,5,6,7,8,9,10,11) 
a: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) 

scala> process(a,b,n) 
res9: List[Int] = List(1, 2, 3, 101, 4, 5, 6, 102, 7, 8, 9, 103, 10, 11) 

scala> val a = List(1,2,3,4,5,6,7,8,9) 
a: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) 

scala> process(a,b,n) 
res10: List[Int] = List(1, 2, 3, 101, 4, 5, 6, 102, 7, 8, 9) 

scala> val a = List(1,2,3,4,5,6,7,8) 
a: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8) 

scala> process(a,b,n) 
res11: List[Int] = List(1, 2, 3, 101, 4, 5, 6, 102, 7, 8) 

---

La vostra richiesta è "Se il primo length Lista è inferiore a n, nessun risultato di inserimento", quindi il mio codice dovrebbe cambiare a:

def process[A](xs: List[A], ys: List[A], n: Int): List[A] = 
    if(xs.size < n || ys.size == 0) xs 
    else xs.take(n):::ys.head::process(xs.drop(n),ys.tail,n) 

Answer 4

Senza scalaz e ricorsione.

scala> a.grouped(n).zip(b.iterator.map{ Some(_) } ++ Iterator.continually(None)).flatMap{ case (as, e) => if (as.size == n) as ++ e else as }.toList 
res17: List[Int] = List(1, 2, 3, 101, 4, 5, 6, 102, 7, 8, 9, 103, 10, 11, 12, 13, 14, 15) 

modo generico:

def filled[T, A, That](a: A, b: Seq[T], n: Int)(implicit bf: CanBuildFrom[A, T, That], a2seq: A => Seq[T]): That = { 
    val builder = bf() 
    builder.sizeHint(a, a.length/n) 
    builder ++= a.grouped(n).zip(b.iterator.map{ Some(_) } ++ Iterator.continually(None)).flatMap{ case (as, e) => if(as.size == n) as ++ e else as } 
    builder.result() 
} 

Usage:

scala> filled("abcdefghijklmnopqrstuvwxyz", "1234", 3) 
res0: String = abc1def2ghi3jkl4mnopqrstuvwxyz 

scala> filled(1 to 15, 101 to 103, 3) 
res1: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3, 101, 4, 5, 6, 102, 7, 8, 9, 103, 10, 11, 12, 13, 14, 15) 

scala> filled(1 to 3, 101 to 103, 3) 
res70: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3, 101) 

scala> filled(1 to 2, 101 to 103, 3) 
res71: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2) 

Answer 5

Questo diventa molto semplice con zipAll.Inoltre, è in grado di scegliere la quantità di elementi del secondo array (in questo caso 1):

val middle = b.grouped(1).toList 
val res = a.grouped(n).toList.zipAll(middle, Nil, Nil) 
res.filterNot(_._1.isEmpty).flatMap(x => x._1 ++ x._2) 

Oppure, se preferite, one-liner:

a.grouped(n).toList.zipAll(b.map(List(_)), Nil, Nil).filterNot(_._1.isEmpty).flatMap(x => x._1 ++ x._2) 

Si può anche fare un classe implicita, quindi è possibile chiamare a.interleave(b, 3) o con un parametro di thrid opzionale a.interleave(b, 3, 1).

Answer 6

Penso che sia la soluzione più semplice.

val bi = b.toIterator 
a.zipWithIndex.flatMap {case (el, i) => 
    if (bi.hasNext && (i-1)%n == n-1) List(bi.next, el) else List(el) 
} 

Answer 7

ecco quello che si desidera:

import scala.annotation.tailrec 

@tailrec 
final def interleave[A](base: Vector[A], a: List[A], b: List[A]): Vector[A] = a match { 
    case elt :: aTail => interleave(base :+ elt, b, aTail) 
    case _ => base ++ b 
} 

... 

interleave(Vector.empty, a, b)