哈斯克爾拆分列表爲兩個由樞軸價值

我想分割[A]爲（[A]，[A]）由樞軸價值，我有我的代碼哈斯克爾拆分列表爲兩個由樞軸價值

splitList :: (Ord a) => a -> [a] -> ([a],[a]) 
splitList pivot list = 
    ([x | x <- list, x <= pivot], [x | x <- list, x > pivot])

但它可以迭代列表兩次以生成兩個列表，是否有一種方法只能迭代一次？

來源

2013-02-08 Ryan

比較http://stackoverflow.com/questions/7641936/is-it-possible-to-do-quicksort-of-a-list-with-only-one-passing。 –

另請參見[Data.List.partition]（http://www.haskell.org/ghc/docs/6.12.1/html/libraries/base/Data-List.html#v%3Apartition） – luqui

有兩種可能，這取決於如果你想有一個tail recursive溶液（和不關心扭轉元素的順序），或者消耗它的參數解決方案lazily。

懶惰的解決方案決定列表的第一個元素是進入第一部分還是進入第二部分，並使用簡單的遞歸來處理列表的其餘部分。這將是在大多數情況下，首選的解決方案爲懶惰通常比尾遞歸更重要：

splitList :: (Ord a) => a -> [a] -> ([a],[a]) 
splitList _ [] = ([], []) 
splitList p (x : xs) 
    | x <= p = (x : l, r) 
    | otherwise = (l, x : r) 
    where 
    ~(l, r) = splitList p xs

但是在我們關心既不是元素，也不是懶惰的排序，而是對速度的情況。（例如在實現時排序算法），然後使用累加器建立結果的變異（見Accumulating Parameters: Getting rid of the 'almost' in "almost tail recursive"）來實現尾遞歸會更合適：

splitListR :: (Ord a) => a -> [a] -> ([a],[a]) 
splitListR pivot = sl ([], []) 
    where 
    sl acc []  = acc 
    sl (l, g) (x : xs) 
     | x <= pivot = sl (x : l, g) xs 
     | otherwise  = sl (l, x : g) xs

來源

2013-02-08 08:16:54

你在where子句中不需要'〜'，綁定已經很懶。 –

@DanielFischer你說得對。當我在單一構造類型上匹配時，我只習慣使用'〜'。 –

import Data.List (partition) 

splitList pivot = partition (<= pivot)

來源

2013-02-08 07:28:15 pat

看起來不錯。但是我對純粹的函數式編程和Haskell很新穎。我想從頭開始編寫例程。 – Ryan

您可以查看庫中'partition「的實現。 http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/Data-List.html#partition – pat

如果你想從頭開始寫這個，你可以維護兩個列表，一個是小項目，一個是大項目。首先，我會寫的包裝：

splitList :: (Ord a) => a -> [a] -> ([a],[a]) 
splitList pivot input = spL input [] [] where

OK，所以我「米只是打電話SPL，給它兩個空列表，開始了因爲我使用的是在那裏塊，我也不需要。通過周圍的支點，所以只有三個列表正在改變獲得通過。如果我們沒有得到任何東西留在輸入，我們就大功告成了，應該返回答案：

spL [] smalls larges = (smalls,larges)

現在，你會看，我們實際上會製造小塊和大塊，所以如果你不喜歡這個，就用最後一個替換對替換（反向小塊，反向大塊）。現在我們來處理一些輸入：

spL (i:input) smalls larges | i <= pivot = spL input (i:smalls) larges 
           | otherwise = spL input smalls (i:larges)

因此，如果它足夠小，我們會將它放在小面前。

推動列表前面的原因是它節省了我們每次迭代到列表的末尾。就像我說的那樣，如果這對你來說很重要，你總是可以扭轉以獲得原來的順序。

所有我們相聚：

splitList :: (Ord a) => a -> [a] -> ([a],[a]) 
splitList pivot input = spL input [] [] where 
    spL [] smalls larges = (smalls,larges) 
    spL (i:input) smalls larges | i <= pivot = spL input (i:smalls) larges 
           | otherwise = spL input smalls (i:larges)

來源

2013-02-08 08:08:16 AndrewC

您可以保留原來的順序，而不必在最後調換結果推之前。 –

它通常被認爲是良好的作風，以避免手工滾動你的遞歸;相反，您可以使用摺疊功能，像這樣：

splitList pivot = foldr triage ([],[]) 
    where 
    triage x ~(lows, highs) 
     | x <= pivot = (x:lows, highs) 
     | otherwise = (lows, x:highs)

當然它甚至更好風格，利用預先存在的函數，它正是你需要的，即分區。:)

來源

2013-02-08 08:25:16

雙人模式應該是懶惰嗎？ –

@WillNess - 好的電話。 –

1976年 http://www.cs.indiana.edu/pub/techreports/TR27.pdf提出以下建議：使用它

import Control.Applicative 

partition3 [] p = ZipList [[], [], []] 
partition3 (x:xs) p 
    | x < p = ZipList [(x:),id,id] <*> partition3 xs p 
    | x > p = ZipList [id,id,(x:)] <*> partition3 xs p 
    | True = ZipList [id,(x:),id] <*> partition3 xs p

，我們寫

splitList pivot list = (a++b, c) 
    where 
     [a,b,c] = getZipList $ partition3 list pivot

所看到here。

來源

2013-03-28 20:56:17

哈斯克爾拆分列表爲兩個由樞軸價值

回答

相關問題