3

[a]をピボット値で（[a]、[a]）に分割したいのですが、コードがあります

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

しかし、リストを2回繰り返して、2つのリストを生成します。一度だけ繰り返す方法はありますか？

4

5 に答える 5

7

末尾再帰ソリューションが必要な場合 (および要素の順序を逆にすることを気にしない場合)、またはその引数を遅延して消費するソリューションが必要な場合に応じて、2 つの可能性があります。

怠惰なソリューションは、リストの最初の要素が最初の部分に入るか、2 番目の部分に入るかを決定し、単純な再帰を使用してリストの残りを処理します。通常、末尾再帰よりも遅延の方が重要であるため、ほとんどの場合、これが推奨される解決策になります。

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

ただし、場合によっては、要素の順序付けも遅延も気にせず、代わりに速度を気にします。(たとえば、並べ替えアルゴリズムを実装する場合。) 次に、アキュムレータを使用して結果を構築するバリアント (「パラメーターの蓄積: 「ほぼ末尾の再帰」の「ほぼ」を取り除く」を参照) を使用して、末尾の再帰を実現する方が適切です。

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

これをゼロから作成する場合は、小さな項目用と大きな項目用の 2 つのリストを維持できます。まず、ラッパーを書きます。

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

では、spL を呼び出して、最初に 2 つの空のリストを指定するだけです。where ブロックを使用しているため、ピボットを渡す必要はなく、変化している 3 つのリストだけが渡されます。入力に何も残っていない場合は完了であり、答えを返す必要があります。

    spL [] 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 に答える