Đuổi qua Swift Sliceable

Question

Tôi cảm thấy rằng tôi phải thiếu điều gì đó hiển nhiên. Phân hủy một danh sách vào đầu và đuôi và sau đó đệ quy trên đuôi là một kỹ thuật lập trình chức năng tiêu chuẩn, nhưng tôi đang đấu tranh để làm điều này cho Sliceable các loại trong Swift.

Tôi có một hàm đệ quy mà sau mô hình này:

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 

} 

Rõ ràng là mã thực hiện rất nhiều hơn thêm mỗi số tiếp theo.

Lưu ý cuộc gọi đến Array(dropFirst(seq)). Việc chuyển đổi sang một mảng là bắt buộc vì dropFirst thực sự trả về một số ArraySlice và ArraySlice không phải là Sliceable, vì vậy tôi không thể chuyển nó vào chức năng của mình.

Tôi không chắc loại trình tối ưu hóa nào của trình biên dịch có khả năng ở đây, nhưng dường như với tôi việc tạo mảng mới từ SubSlice không cần thiết sẽ không tối ưu. Có một giải pháp cho điều này?

Bên cạnh đó, những gì tôi muốn thực sự muốn làm là tạo ra một phiên bản của chức năng này có thể mất bất cứ Sliceable loại:

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 
} 

Lần này tôi không có một giải pháp cho thực tế là tôi có một số SubSlice. Làm thế nào tôi có thể đạt được mục tiêu của mình?

Answer 1

Nó chỉ ra rằng có là một giải pháp chung. Bạn cần phải thêm những yêu cầu chung:

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

Đối với câu hỏi được đăng, điều này mang lại:

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 
} 

Dưới đây là một generic hữu ích giảm trên bất kỳ sliceable:

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 

tôi không thể lấy tín dụng cho điều này, giải pháp là posted trên Diễn đàn phát triển của Apple.

Thật đáng tiếc là các yêu cầu chung chung liên quan đến một hoạt động cơ bản như vậy - nó hầu như không trực quan! Nhưng tôi rất vui khi có giải pháp ...

Answer 2

Tạo một mảng trong mỗi lần lặp lại dường như không phải là một ý tưởng hay. Tôi không biết nếu trình biên dịch tối ưu hóa nó bằng cách nào đó, nhưng bạn có thể có thể tìm thấy một giải pháp khác nhau.

Ví dụ, trong trường hợp này, bạn có thể bỏ de đệ quy và sử dụng một vòng lặp for thay vì sửa đổi mảng tại chỗ.

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

Answer 3

Trên thực tế ArraySlicelàSliceable, vì vậy bạn có thể recurse trên 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 
} 

với một chức năng bao bọc được gọi là một lần duy nhất ở cấp cao nhất:

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

---

Tôi không có giải pháp cho vấn đề chung thứ hai của bạn. Các tài liệu API cho Sliceable trạng thái đó SubSlicenên được Sliceable chính nó (đó là trường hợp cho tất cả biết đến Sliceable loại).

tôi do đó có cảm giác rằng chúng ta có thể bằng cách yêu cầu rằng T.SubSlice là chính nó sliceable với giống SubSlice loại, tuy nhiên điều này không biên dịch:

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 
} 

Trình biên dịch chấp nhận rằng dropFirst(list) có thể được đúc đến T.SubSlice, nhưng từ chối gọi recurseSeq() trên giá trị đó, mà tôi không hiểu.

---

Ngoài ra, bạn có thể recurse trên 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 
} 

với một wrapper mà phải mất một SequenceType:

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

Mảng và mảng tất cả các lát phù hợp với SequenceType, do đó nên hoạt động trong tất cả các trường hợp của bạn.