Come sarebbe un approccio funzionale allo spostamento di determinati elementi dell'array?

Question

Ho un'app Scala con un elenco di elementi con caselle di controllo, quindi l'utente ne seleziona alcuni e fa clic su un pulsante per spostarli di una posizione in alto (a sinistra). Ho deciso di scrivere una funzione per spostare elementi di un tipo arbitrario che soddisfano un dato predicato. Quindi, se si dispone di questi elementi:

a b c D E f g h I 

e il predicato è "caratteri maiuscoli", la funzione potrebbe restituire questo:

a b D E c f g I h 

In breve, qualsiasi sequenza di elementi contigui che soddisfano il predicato sono scambiato con il singolo elemento a sinistra di esso.

Mi è venuta la seguente brutta implementazione imperativa. Mi piacerebbe vedere una soluzione funzionale, e, si spera, leggibile.

def shiftUp[T](a:Array[T], shiftable: T => Boolean) = { 
    val s = new Array[T](a.length) 
    var i = 0 
    var j = 0 
    while(i < a.length) 
    { 
     if(!shiftable(a(i)) && i < a.length - 1 && shiftable(a(i+1))) 
     { 
      var ii = i + 1 
      while(ii < a.length && shiftable(a(ii))) 
      { 
       s(j) = a(ii) 
       ii = ii+1 
       j = j+1 
      } 
      s(j) = a(i) 
      i = ii 
     } 
     else 
     { 
      s(j) = a(i) 
      i = i+1 
     } 
     j = j+1 
    } 
    s 
} 

EDIT: Grazie a tutti, spero che vi sia piaciuto l'esercizio!

Answer 1

Ecco un'implementazione puramente funzionale

def shiftElements[A](l: List[A], pred: A => Boolean): List[A] = { 
    def aux(lx: List[A], accum: List[A]): List[A] = { 
    lx match { 
     case Nil => accum 
     case a::b::xs if pred(b) && !pred(a) => aux(a::xs, b::accum) 
     case x::xs => aux(xs, x::accum) 
    } 
    } 
    aux(l, Nil).reverse 
} 

Ed ecco uno che utilizza mutevolezza al suo interno per essere più veloce

import scala.collection.mutable.ListBuffer 
def shiftElements2[A](l: List[A], pred: A => Boolean): List[A] = { 
    val buf = new ListBuffer[A] 
    def aux(lx: List[A]) { 
    lx match { 
     case Nil =>() 
     case a::b::xs if pred(b) && !pred(a) => { 
     buf.append(b) 
     aux(a::xs) 
     } 
     case x::xs => { 
     buf.append(x) 
     aux(xs) 
     } 
    } 
    } 
    aux(l) 
    buf.toList 
} 

Answer 2

Probabilmente si potrebbe fare questo attraverso un foldLeft (noto anche come /:):

(str(0).toString /: str.substring(1)) { (buf, ch) => 
    if (ch.isUpper) buf.dropRight(1) + ch + buf.last else buf + ch 
} 

ha bisogno di lavorare per gestire la stringa vuota, ma:

def foo(Str: String)(p: Char => Boolean) : String = (str(0).toString /: str.substring(1)) { 
    (buf, ch) => if (p(ch)) buf.dropRight(1) + ch + buf.last else buf + ch 
} 

val pred = (ch: Char) => ch.isUpper 
foo("abcDEfghI")(pred) //prints abDEcfgIh 

Lascio come esercizio su come modificare questo nella soluzione basata su array

Answer 3

Non

il più veloce, ma non limitato a String e utilizzando la stessa logica @oxbow_lakes

def shift[T](iter: Iterable[T])(p: T=>Boolean): Iterable[T] = 
    iter.foldLeft(Iterable[T]())((buf, elm) => 
    if (p(elm) && buf.nonEmpty) 
     buf.dropRight(1) ++ Iterable[T](elm) ++ Iterable[T](buf.last) 
    else 
     buf++Iterable[T](elm) 
) 

def upperCase(c:Char)=c.isUpper 

shift("abcDEfghI")(upperCase).mkString 
    //scala> res86: String = abDEcfgIh 

val array="abcDEfghI".toArray 
shift(array)(upperCase).toArray 
    //res89: Array[Char] = Array(a, b, D, E, c, f, g, I, h) 

def pair(i:Int)=i%2==0 
val l=List(1,2,3,5,4,6,7,9,8) 
shift(l)(pair) 
    //scala> res88: Iterable[Int] = List(2, 1, 3, 4, 6, 5, 7, 8, 9) 

Answer 4

I non reclamare questa roba qui sotto per essere efficiente o leggibile. Sfortunatamente, tutte le buone risposte sembrano essere prese, quindi vado per l'originalità. :-)

def shift[T](a: Seq[T], p: T => Boolean) = { 
    val (areP, notP) = a.zipWithIndex partition { case (t, index) => p(t) } 
    val shifted = areP map { case (t, index) => (t, index - 1) } 
    val others = notP map (shifted.foldLeft(_){ 
    case ((t, indexNotP), (_, indexIsP)) => 
     if (indexNotP == indexIsP) (t, indexNotP + 1) else (t, indexNotP) 
    }) 
    (shifted ++ others).sortBy(_._2).map(_._1) 
} 

Quindi, ecco cosa sta succedendo. Innanzitutto, associo ciascun carattere al suo indice (a.zipWithIndex), quindi separo in areP e notP a seconda che il carattere soddisfi o meno p.

Quindi, a questo punto, ho due sequenze, ciascuna composta da un carattere e il suo indice nella sequenza originale.

Successivamente, ho semplicemente spostato l'indice degli elementi nella prima sequenza, sottraendo 1 e calcolando shifted.

Il calcolo del nuovo indice degli elementi non modificati è molto più difficile. Per ognuno di questi elementi (notP map), eseguirò un foldLeft. L'accumulatore della piega a sinistra sarà l'elemento stesso (sempre con il suo indice).La sequenza che viene piegata è la sequenza di elementi spostati - così si può vedere che per ogni elemento non spostato, ho attraversato l'intera sequenza di elementi spostati (altamente inefficienti!).

Quindi, confrontiamo l'indice dell'elemento non spostato all'indice di ogni elemento spostato. Se sono uguali, aumenta l'indice dell'elemento non spostato. Poiché la sequenza di elementi spostati è ordinata (partition non cambia l'ordine), sappiamo che testeremo prima per gli indici più bassi, e poi per gli indici più alti, garantendo che un elemento avrà il suo indice aumentato quanto necessario.

Con ciò, uniamo le due sequenze, le ordiniamo in base ai nuovi indici e quindi eseguiamo il mapping all'elemento.

Answer 5

Modifica: questo in realtà non risolve il problema posto: risolve un problema correlato ma diverso (alzando la priorità degli elementi contrassegnati di uno). Lo sto lasciando qui per riferimento, tuttavia.

---

Ecco un "one-liner", utilizzando gli array come richiesto, per Scala 2.8.

def shiftUp[T](a: Array[T], p: T => Boolean) = { 
    a.zipWithIndex.map(ci => { 
    (ci._1 , if (p(ci._1)) ci._2 - 1.5 else ci._2.toDouble) 
    }).sortWith((l,r) => l._2 < r._2).map(_._1) 
} 

scala> shiftUp(Array('h','E','l','l','O'),(c:Char)=>c.isUpper).toArray 
res0: Array[Char] = Array(E, h, l, O, l) 

scala> shiftUp("HeLlO".toArray,(c:Char)=>c.isUpper).toArray 
res1: Array[Char] = Array(H, L, e, O, l) 

lascio come esercizio al lettore per capire come funziona. (Se si vuole veramente farmaci generici con T, in Scala 2.8 sta andando per darvi un GenericArray, si può quindi ToArray se si desidera un Java gamma potenzialmente primitiva.)

Answer 6

Ecco un'altra variante sulla risposta di Geoff:

def shift[T](l: List[T], p: T => Boolean): List[T] = { 
    l match { 
    case a::b::t if ! p(a) && p(b) => b::shift(a::t, p) 
    case a::t => a::shift(t, p) 
    case Nil => l 
    } 
} 

rapidamente testata utilizzando

scala> def pred(c: Char) = c.isUpper 
pred: (c: Char)Boolean 

scala> shift("abcDEfghI".toList, pred) 
res3: List[Char] = List(a, b, D, E, c, f, g, I, h) 

scala> shift("AbCd".toList, pred) 
res4: List[Char] = List(A, C, b, d) 

scala> shift(Nil, pred) 
res5: List[Nothing] = List() 

Ecco versione a due

def shift[T](l: List[T], p: T => Boolean, r: List[T] = Nil): List[T] = { 
    l match { 
    case a::b::t if ! p(a) && p(b) => shift(a::t, p, b::r) 
    case a::t => shift(t, p, a::r) 
    case Nil => r.reverse 
    } 
} 

Answer 7

Non so abbastanza per scriverlo in Scala, ma questo problema è fatto su misura per le funzioni di lista takeWhile e dropWhile. L'idea è quella di dividere l'elenco delle voci in tre parti:

• parte sinistra, calcolati con takeWhile, contiene elementi più a sinistra che non soddisfano il predicato.

• La parte centrale è il gruppo di elementi che si desidera spostare a sinistra, calcolati eliminando gli elementi di sinistra e quindi takeWhile il resto.

• La parte destra è tutto finito; dropWhile gli elementi centrali.

Qui è in Haskell:

-- take first group of elements satisfying p and shift left one 
shift :: (a -> Bool) -> [a] -> [a] 
shift p l = case reverse left of 
       []  -> l 
       (a:as) -> reverse as ++ middle ++ a : shift p right 
    where left = takeWhile (not . p) l -- could be done with List.break 
     notLeft = dropWhile (not . p) l 
     middle = takeWhile p notLeft -- could be done with List.span 
     right = dropWhile p notLeft 

Ed ecco una singola prova di unità:

*Shiftup> shift (>9) [1, 2, 3, 44, 55, 6, 7, 8] 
[1,2,44,55,3,6,7,8] 

Haskell programmatori potrebbero utilizzare List.break o List.span per combinare le chiamate per takeWhile e dropWhile, ma Non sono sicuro che Scala abbia queste cose. Inoltre, takeWhile e dropWhile sono bei nomi significativi, mentre io trovo almeno break e span meno visibili.

EDIT: fissato chiamata ricorsiva per fare shift p right invece di right per scalare una marcia tutti i gruppi.

Answer 8

Questo è fondamentalmente un algoritmo imperativo con uno stile funzionale.

def shifWithSwap[T](a: Array[T], p: T => Boolean) = { 
    def swap(i:Int, j:Int) = { 
    val tmp = a(i); a(i) = a(j); a(j) = tmp 
    } 
    def checkAndSwap(i:Int) = i match { 
    case n if n < a.length - 1 && !p(a(i)) && p(a(i+1)) => swap(i, i+1) 
    case _ => 
    } 
    (0 until a.length - 1) map checkAndSwap 
    a 
} 

Modifica l'array in posizione, con un effetto collaterale. Penso che sia davvero come la versione della domanda, tranne che è più facile da leggere. Imperativo non deve essere brutto ...

Edit: Peccato, non riusciva a prendere sonno fino a quando ho scritto questo verso il basso (come sopra, solo più compatta):

def shift[T](a: Array[T], p: T => Boolean) = { 
    for (i <- 0 until a.length - 1; if !p(a(i)) && p(a(i+1))) { 
    val tmp = a(i); a(i) = a(i+1); a(i+1) = tmp // swap 
    } 
    a 
} 

Answer 9

Una soluzione in J:

('abcdefghijklmnopqrstuvwxyz';'ABCDEFGHIJKLMNOPQRSTUVWXYZ') (4 : '(y#~y e. >1{x)([: I. '' ''= ])} }._1&|.&.((1,~y e. >0{x)&#)y,'' ''') 'abcDEfghI' 
abDEcfgIh 

Rompiamo questo in pezzi nominati per una più facile comprensione. La stringa finale "abDEcfgIh" è il risultato dell'applicazione di una funzione alla stringa "abcDEfghI" che è l'argomento corretto per la funzione. La coppia di alfabeti costituiscono l'argomento di sinistra alla funzione (che è la parte iniziale “(4 : ...”) Quindi, al posto del 2-vettore elemento di stringhe in scatola, potremmo citare singolarmente:.

'lc uc'=. 'abcdefghijklmnopqrstuvwxyz';'ABCDEFGHIJKLMNOPQRSTUVWXYZ' 

Ora che abbiamo due variabili "lc" e "uc" per gli alfabeti minuscoli e maiuscoli, esaminiamo il corpo della funzione in dettaglio. Prendendo un pezzo logicamente coerente dall'estremità destra, poiché questo sarebbe valutato per prima cosa, potremmo chiamarlo così:

rmUCshift=: 4 : 0 
    }._1&|.&.((1,~y e. >0{x)&#)y,' ' 
) 

Definisce "rmUCshift "come qualcosa che richiede un argomento a destra e a sinistra (lo" 4 : "specifica questo) con il corpo che inizia alla riga successiva e continua fino al paren di chiusura nuda. Il modulo "4 : 0", seguito dal corpo, è una variante del modulo "corpo" "4 :" mostrato inizialmente. Questo verbo rmUCshift può essere richiamato indipendentemente simili:

(lc;'') rmUCshift 'abcDEfghI' NB. Remove upper-case, shift, then insert 
ab cfg h       NB. spaces where the upper-case would now be. 

L'invocazione è rientrato tre spazi e l'uscita segue immediatamente esso. L'argomento di sinistra (lc;'') è un vettore a due elementi con l'array vuoto specificato come secondo elemento perché non è utilizzato in questo pezzo di codice - potremmo aver utilizzato qualsiasi valore dopo il punto e virgola ma le due virgolette singole sono facili da digitare.

I prossimi pezzi a nome sono questi (definizioni seguiti da esempi):

ixSpaces=: [:I.' '=] 
    ixSpaces 'ab cfg h' 
2 3 7 
    onlyUC=: 4 : 'y#~y e.>1{x' 
    ('';uc) onlyUC 'abcDEfghI' 
DEI 

La combinazione di questi pezzi denominati insieme ci dà questa:

(lc;uc) (4 : '(x onlyUC y)(ixSpaces x rmUCshift y)}x rmUCshift y') 'abcDEfghI' 
abDEcfgIh 

Tuttavia, la ripetizione di “x rmUCshift y” è non necessario e può essere semplificato per darci questo:

(lc;uc) (4 : '(x onlyUC y) ((ixSpaces ]) } ]) x rmUCshift y') 'abcDEfghI' 
abDEcfgIh