list - Haskell: リスト境界

Question

新しいリスト（someList）に追加したいdouble（myList）のリストがありますが、新しいリストが設定サイズ、つまり25に達したら、追加をやめたいと思います。sum を使用してこの関数を実装しようとしましたが、失敗しました。以下のコード例。
someList = [(a)| a <- myList, sum someList < 30]

Answer 1

@DanielFischerが質問を表現した方法は、Haskellの考え方と互換性があります。

someListを、合計が30未満のmyListの最長のプレフィックスにしますか？

これが私がそれにアプローチする方法です：私たちのリストが

>>> let list = [1..20]

以下を使用して「累積合計」を見つけることができます。

>>> let sums = tail . scanl (+) 0
>>> sums list
[1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210]

次に、元のリストでそれを圧縮して、その時点までの合計を持つ要素のペアを取得します

>>> zip list (sums list)
[(1,1),(2,3),(3,6),(4,10),(5,15),(6,21),(7,28),(8,36),
 (9,45),(10,55),(11,66),(12,78),(13,91),(14,105),(15,120),
 (16,136),(17,153),(18,171),(19,190),(20,210)]

次に、takeWhileこのリストを使用して、必要なプレフィックスを取得できます。

>>> takeWhile (\x -> snd x < 30) (zip list (sums list))
[(1,1),(2,3),(3,6),(4,10),(5,15),(6,21),(7,28)]

最後に、この計算を実行するために使用した累積合計を取り除くことができます。

>>> map fst (takeWhile (\x -> snd x < 30) (zip list (sums list)))
[1,2,3,4,5,6,7]

怠惰のため、これは再帰的ソリューションと同じくらい効率的であることに注意してください。テストに失敗するまでの合計のみを計算する必要があります。これは、ソリューションが無限のリストで機能するためにわかります（すべての合計を計算する必要がある場合、終了することはないため）。

私はおそらくこれを抽象化し、パラメータとして制限を取ります：

>>> :{
... let initial lim list =
...        map fst (takeWhile (\x -> snd x < lim) (zip list (sums list)))
... :}

この関数には、満たす必要のある明らかな特性があります。つまり、リストの合計は常に制限よりも小さい必要があります（制限が0より大きい場合）。したがって、QuickCheckを使用して、正しく実行されたことを確認できます。

>>> import Test.QuickCheck
>>> quickCheck (\lim list -> lim > 0 ==> sum (initial lim list) < lim)
+++ OK, passed 100 tests.

Answer 2

あなたが望む行動は

ghci> appendWhileUnder 25 [1..5] [1..5]
[1,2,3,4,5,1,2,3]

合計すると 21 になり、4 を足すと 25 になるからです。

OK、これを行う1つの方法は、それらを追加して++から、25未満の最初のセグメントを取ることです.

appendWhileUnder n xs ys = takeWhileUnder n (xs++ys)

中間リストを合計し続けたくないので、許可されている量を追跡します ( n)。

takeWhileUnder n [] = []
takeWhileUnder n (x:xs) | x < n = x:takeWhileUnder (n-x) xs
                        | otherwise = []

ここでxは、許容量の残りを超えない場合は通過を許可します。

おそらく望ましくない副作用: 合計が 25 を超えると、元のリストのビットが切り捨てられます。

appendWhileUnder' n xs ys = xs ++ takeWhileUnder (n - sum xs)

xsそれがあなたを連れてくるかどうかにかかわらず、全体を保ちますn。

Answer 3

someList = makeList myList [] 0 where
    makeList (x:xs) ys total = let newTot = total + x
                               in if newTot >= 25
                                  then ys
                                  else makeList xs (ys ++ [x]) newTot

これは、合計が 25 未満である限り、myList から要素を取得します。

ロジックは で行われmakeListます。入力リストの最初の要素を取得し、現在の合計に追加して、25 より大きいかどうかを確認します。25 より大きい場合は、出力リストに追加するべきではなく、再帰を終了します。それ以外の場合xは、出力リスト ( ys) の最後に配置し、残りの入力リストを続行します。