哈斯克尔拆分列表为两个由枢轴价值

我想分割[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

哈斯克尔拆分列表为两个由枢轴价值

回答

相关问题