Haskell，从列表元组中拉出两个列表

Question

我正在使用2个辅助函数进行“合并排序”。第一个辅助函数将列表拆分成一个列表元组，将奇数和偶数索引放在单独的列表中。

Example: [1,2,3,4,5,6] 
Returns: ([1,3,5],[2,4,6]) 

第二个帮助函数假定列表已排序并合并它们。

我要使用这两个函数实现未排序列表的合并排序。

我有这个非常低效率的片断，基本上分割（长度 - 1）* 2次并合并列表（长度 - 1）次。

sort length (z:zs) 
     | length == 0 = (z:zs) 
     | otherwise = sort (length - 1) (merge (fst (split(z:zs))) (snd (split(z:zs))) 

我打电话分裂两次，得到这是第一个分割做了同样的信息，我不会递归远远不够（其中每个列表仅仅是一个单，然后将它们合并所有）。

我该如何递归到单例情况并同时拉出元组的两个元素？

非常感谢您提供的任何帮助。

Answer 1

可以使用uncurry到merge转换到未咖喱函数并传递split(z:zs)作为参数：

sort (length - 1) $ uncurry merge $ split (z:zs) 

的uncurry函数变换a -> b -> c类型的功能到(a, b) -> c类型的功能。在你的情况merge有型号[a] -> [a] -> [a]而uncurry merge有型号([a], [a]) -> [a]和([a], [a])是split的返回类型。

或者，也可以简单地使用let或where条款提及的split结果：

let (left, right) = split (z:zs) 
in sort (length - 1) $ merge left right 

这是一个改进版本：

let res = split (z:zs) 
in sort (length - 1) $ merge (fst res) (snd res) 

---

作为一个边注意您的sort功能不正确。你的定义是这样的：

sort length (z:zs) = ... 

然而，这仅匹配非空列表。当它永远不会发生时，考虑length == 0的情况也是无用的。

你sort outght的定义来考虑空的情况下也：