swift - 使用 Haskell 风格快速排序

Question

我正在快速实现快速排序算法。基本上我想达到一些 Haskell 风格的清晰度。这是到目前为止我可以开发的代码:

func quickSort<T: Comparable>(list: [T]) -> [T] {
    if list.isEmpty {
        return []
    } else {
        let head = list[0]
        return quickSort(list.filter {$0 <= head}) + [head] + quickSort(list.filter {$0 > head})
    }
}

我们可以改进这段代码，使其看起来更像 Haskell 风格吗？您有什么建议？

Answer 1

好吧，如果你想要复制的 Haskell 看起来像这样:

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerOrEqual = filter (<= x) xs
        greater = filter (> x) xs
    in  quicksort smallerOrEqual ++ [x] ++ quicksort greater

您可以添加此 Swift Array 扩展(我 stole from objc.io ):

extension Array {
    var decompose : (head: T, tail: [T])? {
        return (count > 0) ? (self[0], Array(self[1..<count])) : nil
    }
}

然后做这样的事情:

func recursiveQuicksort<T: Comparable>(inputArray:Array<T>) -> Array<T> {
    if let (x, xs) = inputArray.decompose {
        let smallerOrEqual = xs.filter{$0 <= x}
        let greater = xs.filter{$0 > x}
        return recursiveQuicksort(smallerOrEqual) + [x] + recursiveQuicksort(greater)
    } else {
        return inputArray
    }
}

该扩展为您提供了一点点模式匹配，以更接近 Haskell，其余的很容易看出它如何在两种语言之间映射。不过，Haskell 的语法仍然更加简洁。