嵌套函数崩溃雨燕编译

Question

我写了一个递归mergeSort功能：

func mergeSort<T: Comparable>(inout array: [T]) { 
    if array.count <= 1 { 
     return 
    } 

    var leftSlice = [T](array[0..<array.count/2]) 
    var rightSlice = [T](array[array.count/2...array.endIndex - 1]) 

    mergeSort(&leftSlice) 
    mergeSort(&rightSlice) 
    array = merge(leftSlice, rightSlice) 
} 

func merge<T: Comparable>(var left: [T], var right: [T]) -> [T] { 
    var mergedValues = [T]() 

    while !left.isEmpty && !right.isEmpty { 
     mergedValues.append(left.first! < right.first! ? left.removeAtIndex(0) : right.removeAtIndex(0)) 
    } 

    if !left.isEmpty { 
     mergedValues += left 
    } else if !right.isEmpty { 
     mergedValues += right 
    } 

    return mergedValues 
} 

现在，由于merge()只应该由mergeSort()使用我把它的mergeSort()内，因此使merge()一个nested function：

func mergeSort<T: Comparable>(inout array: [T]) { 
    func merge<T: Comparable>(var left: [T], var right: [T]) -> [T] { 
     var mergedValues = [T]() 

     while !left.isEmpty && !right.isEmpty { 
      mergedValues.append(left.first! < right.first! ? left.removeAtIndex(0) : right.removeAtIndex(0)) 
     } 

     if !left.isEmpty { 
      mergedValues += left 
     } else if !right.isEmpty { 
      mergedValues += right 
     } 

     return mergedValues 
    } 

    if array.count <= 1 { 
     return 
    } 

    var leftSlice = [T](array[0..<array.count/2]) 
    var rightSlice = [T](array[array.count/2...array.endIndex - 1]) 

    mergeSort(&leftSlice) 
    mergeSort(&rightSlice) 
    array = merge(leftSlice, rightSlice) 
} 

现在first版本正常工作，但second一个没有。
这怎么可能？

Answer 1

看起来你已经发现，在涉及到嵌套泛型函数编译器的错误。这里有一个减少也崩溃了1.2编译器：

func f<T>(t: T) { 
    func g<U>(u: U) { } 
} 

但在这种情况下，你实际上并不需要的merge一个仿制版本。其通用参数与外部功能相同，因此只是使用该功能：

func mergeSort<T: Comparable>(inout array: [T]) { 
    // no generic placeholder needed, T is the T for mergeSort 
    func merge(var left: [T], var right: [T]) -> [T] { 
     // etc. 
    } 
} 

这似乎工作正常。

然而，这也是值得指出的是，在你的merge功能，你调用一个循环中，这是一个O（n）的功能removeAtIndex。这意味着你的合并排序不会有希望的复杂性。

这里有一个替代版本考虑：

func mergeSort<T: Comparable>(inout array: [T], range: Range<Int>? = nil) { 

    func merge(left: Range<Int>, right: Range<Int>) -> [T] {  
     var tmp: [T] = [] 
     tmp.reserveCapacity(count(left) + count(right)) 

     var l = left.startIndex, r = right.startIndex 

     while l != left.endIndex && r != right.endIndex { 
      if array[l] < array[r] { 
       tmp.append(array[l++]) 
      } 
      else { 
       tmp.append(array[r++]) 
      } 
     } 
     // where left or right may be empty, this is a no-op 
     tmp += source[l..<left.endIndex] 
     tmp += source[r..<right.endIndex] 

     return tmp 
    } 

    // this allows the original caller to omit the range, 
    // the default being the full array 
    let r = range ?? indices(array) 
    if count(r) > 1 { 
     let mid = r.startIndex.advancedBy(r.startIndex.distanceTo(r.endIndex)/2) 
     let left = r.startIndex..<mid 
     let right = mid..<r.endIndex 

     mergeSort(&array, range: left) 
     mergeSort(&array, range: right) 
     let merged = merge(left, right) 
     array.replaceRange(r, with: merged) 
    } 
} 

我也想说，既然merge可能是在自己的权利的统称有用的功能，你可能也使其独立，而不是嵌套它（在执行快速排序时类似地，partition）。嵌套不会给你买任何东西（除了上面引用外部参数的技巧之外，这可能是一个糟糕的做法，无论如何，我主要是这样做，以表明你可以:)

Answer 2

您不需要使merge成为通用功能。通用T已经为mergeSort定义，所以你只需设置[T]作为内部函数将参数：

func merge(var left: [T], var right: [T]) -> [T] { 
    var mergedValues = [T]() 
    ... 
}