Haskell，從列表元組中拉出兩個列表

我正在使用2個輔助函數進行「合併排序」。第一個輔助函數將列表拆分成一個列表元組，將奇數和偶數索引放在單獨的列表中。Haskell，從列表元組中拉出兩個列表

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)))

我打電話分裂兩次，得到這是第一個分割做了同樣的信息，我不會遞歸遠遠不夠（其中每個列表僅僅是一個單，然後將它們合併所有）。

我該如何遞歸到單例情況並同時拉出元組的兩個元素？

非常感謝您提供的任何幫助。

來源

2014-10-06 Aserian

看看'where'或'let'結構。使用'where（first，second）= split ...'之類的東西。另外，你可以使用這樣的結構'all @（x：xs）'將變量綁定到整個列表。 – Mark 2014-10-06 05:31:43

'length'參數實現了什麼？ – 2014-10-06 05:46:17

如果您有其他問題，請將其作爲新問題發佈，並且不要將其添加到現有問題中。 – Bakuriu 2014-10-06 05:53:33

可以使用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的定義來考慮空的情況下也：

來源

2014-10-06 05:51:21 Bakuriu

我希望有一天，所有的事情都對我有意義！現在，謝謝你！ – Aserian 2014-10-06 05:56:30

當uncurry被應用於arity大於2的函數時，它的行爲是什麼？ – Mark 2014-10-06 06:08:43

@標準答案是，在Haskell中，每個函數都只有一個（一個）。所以'a-> b-> c ===>（a，b） - > c'中的'c'也可以是'd-> e-> f - > ...'。 – 2014-10-06 06:32:35

Haskell，從列表元組中拉出兩個列表

回答

相關問題