Ricorsione su Swift Sliceable

Question

Sento che mi manca qualcosa di ovvio. Scomporre una lista in testa e coda e poi ricorrere sulla coda è una tecnica di programmazione funzionale standard, eppure sto cercando di farlo per i tipi Sliceable in Swift.

Ho una funzione ricorsiva che segue questo schema:

func recurseArray(arr: [Int]) -> [Int] { 

    guard let first = arr.first else { 
     return [] 
    } 

    let rest = recurseArray(Array(dropFirst(arr))) 
    let next = rest.first ?? 0 

    return [first + next] + rest 

} 

Ovviamente il codice vero e proprio fa molto di più che aggiungere ogni numero a quello successivo.

Nota la chiamata a Array(dropFirst(seq)). La conversione in un array è richiesta poiché dropFirst restituisce effettivamente un ArraySlice e un ArraySlice non è un Sliceable, quindi non posso passarlo alla mia funzione.

Non sono sicuro del tipo di ottimizzazione che il compilatore è in grado di eseguire qui, ma mi sembra che la creazione di un nuovo array da un SubSlice non sia necessariamente ottimale. c'è una soluzione a questo?

Inoltre, quello che mi piacerebbe davvero piace fare è creare una versione di questa funzione che può assumere qualsiasi Sliceable tipo:

func recurseSeq<T: Sliceable where T.Generator.Element == Int>(list: T) -> [Int] { 

    guard let first = list.first else { 
     return [] 
    } 

    let rest = recurseSeq(dropFirst(list)) // <- Error - cannot invoke with argument type T.SubSlice 
    let next = rest.first ?? 0 

    return [first + next] + rest 
} 

Questa volta non ho una soluzione al Infatti ho un SubSlice. Come posso raggiungere il mio obiettivo?

Answer 1

Si scopre che lo è una soluzione generica. È necessario aggiungere questi requisiti generici:

< 
    S : Sliceable where S.SubSlice : Sliceable, 
    S.SubSlice.Generator.Element == S.Generator.Element, 
    S.SubSlice.SubSlice == S.SubSlice 
    > 

per la domanda pubblicata, questo dà:

func recurseSeq< 
    S : Sliceable where S.SubSlice : Sliceable, 
    S.SubSlice.Generator.Element == Int, 
    S.SubSlice.SubSlice == S.SubSlice, 
    S.Generator.Element == Int 
    >(list: S) -> [Int] { 

    guard let first = list.first else { 
     return [] 
    } 

    let rest = recurseSeq(dropFirst(list)) 
    let next = rest.first ?? 0 

    return [first + next] + rest 
} 

Ecco un utile generica ridurre in qualsiasi affettabili:

extension Sliceable where 
    SubSlice : Sliceable, 
    SubSlice.Generator.Element == Generator.Element, 
    SubSlice.SubSlice == SubSlice { 

    func recReduce(combine: (Generator.Element, Generator.Element) -> Generator.Element) -> Generator.Element? { 

    return self.first.map { 
     head in 
     dropFirst(self) 
     .recReduce(combine) 
     .map {combine(head, $0)} 
     ?? head 
    } 
    } 
} 
[1, 2, 3].recReduce(+) // 6 

non posso prendersi il merito di questo, la soluzione è stata posted sui forum di sviluppo Apple.

È un peccato che i requisiti generici siano così coinvolti per un'operazione di base - non è quasi intuitivo! Ma sono contento di avere una soluzione ...

Answer 2

La creazione di un array in ogni iterazione non sembra una buona idea. Non so se il compilatore lo ottimizzi in qualche modo, ma probabilmente potresti trovare una soluzione diversa.

Ad esempio, in questo caso, è possibile eliminare la ricorsione e utilizzare invece un ciclo for che modifica l'array in posizione.

func recurseArray2(var a: [Int]) -> [Int] { 
    for var i = a.count-1; i > 0; i-- { 
     a[i-1] += a[i] 
    } 
    return a 
} 

Answer 3

realtà ArraySliceèSliceable, in modo da poter recurse su ArraySlice<Int>:

func recurseArray(arr: ArraySlice<Int>) -> [Int] { 

    guard let first = arr.first else { 
     return [] 
    } 

    let rest = recurseArray(dropFirst(arr)) 
    let next = rest.first ?? 0 

    return [first + next] + rest 
} 

con una funzione wrapper che viene chiamato solo una volta al livello più alto:

func recurseArray(arr: [Int]) -> [Int] { 
    return recurseArray(arr[arr.startIndex ..< arr.endIndex]) 
} 

---

Non ho una soluzione per il tuo secondo problema più generale. La documentazione API per Sliceable stato che SubSlicedovrebbe essere Sliceable stesso (che è il caso di tutti conosciuti Sliceable tipi).

Ho pertanto la sensazione che dovrebbe essere possibile Richiedendo che T.SubSlice è esso stesso affettabili con l'identico SubSlice tipo, tuttavia questo non elaborano:

func recurseSeq<T: Sliceable where T.Generator.Element == Int, 
    T.SubSlice : Sliceable, 
    T.SubSlice.SubSlice == T.SubSlice>(list: T.SubSlice) -> [Int] { 

     guard let first = list.first else { 
      return [] 
     } 
     let rest = recurseSeq(dropFirst(list) as T.SubSlice) 
     // error: cannot invoke 'recurseSeq' with an argument list of type '(T.SubSlice)' 

     let next = rest.first ?? 0 

     return [first + next] + rest 
} 

Il compilatore accetta che dropFirst(list) può essere gettato a T.SubSlice, ma si rifiuta di chiamare recurseSeq() su quel valore, che io non capisco .

---

In alternativa, si può recurse su un GeneratorType:

func recurseGen<G: GeneratorType where G.Element == Int>(inout gen: G) -> [Int] { 

    guard let first = gen.next() else { 
     return [] 
    } 
    let rest = recurseGen(&gen) 
    let next = rest.first ?? 0 
    return [first + next] + rest 
} 

con un wrapper che prende un SequenceType:

func recurseSeq<T: SequenceType where T.Generator.Element == Int>(list: T) -> [Int] { 
    var gen = list.generate() 
    return recurseGen(&gen) 
} 

Array e fette di array sono tutti conformi alle SequenceType, in modo che dovrebbe funziona in tutti i tuoi casi.