3

我想通过一个枢轴值将 [a] 拆分为 ([a], [a]) 并且我有我的代码

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

但是它迭代列表两次以生成两个列表，有没有办法只迭代一次？

4

5 回答 5

7

有两种可能性，取决于您是想要一个尾递归解决方案（并且不关心反转元素的顺序），还是一个懒惰地消耗其参数的解决方案。

惰性解决方案决定列表的第一个元素是进入第一部分还是进入第二部分，并使用简单的递归来处理列表的其余部分。在大多数情况下，这将是首选解决方案，因为惰性通常比尾递归更重要：

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-08T08:16:54.553 回答
3

通常认为避免手动滚动递归是一种很好的风格；相反，您可以使用如下折叠功能：

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

当然，使用完全符合您需要的预先存在的功能（即分区）是更好的风格。:)

于 2013-02-08T08:25:16.413 回答
2

如果你想从头开始写，你可以维护两个列表，一个用于小项目，一个用于大项目。首先，我将编写包装器：

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

好的，所以我只是调用 spL 并给它两个空列表开始。因为我使用的是 where 块，我不需要传递枢轴，所以只有三个正在改变的列表被传递. 如果我们在输入中没有留下任何东西，我们就完成了，应该返回答案：

    spL [] smalls larges = (smalls,larges)

现在正如您所看到的，我们实际上会将 smalls 和 larges 倒过来，所以如果您不喜欢这样，请将那里的最终答案对替换为 (reverse smalls,reverse 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-08T08:08:16.180 回答
1 
import Data.List (partition)

splitList pivot = partition (<= pivot)
于 2013-02-08T07:28:15.567 回答
0

http://www.cs.indiana.edu/pub/techreports/TR27.pdf of 1976 1建议如下：

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

1如此处所示。

于 2013-03-28T20:56:17.753 回答