haskell foldr與列表操作

Question

給定一個負數和正數的序列列表，如何使用foldr將它們分成負數和負數序列？例如[1,2,3，-1，-2，-3,1,2,3]我會得到[[1,2,3]，[ - 1，-2，-3] [1,2,3]

一些疑慮

我怎麼知道以前的分區，我已經比較，如果相同的符號之一，我比較當前的？

如何將元素添加到列表中？我嘗試了類似[x]：y的東西，但我得到的是每個元素作爲列表並連接在一起，這不是結果。

什麼我目前是這個

foldr (\ x y -> if x >= 0 then [x]:y else y) [[]] 

這是不對的

提前爲幫助非常感謝。

Answer 1

使用最好的工具來完成這項工作。在這種情況下，這項工作的最佳工具是groupBy。

groupBy將列表的兩個成員傳遞給你的函數，所以你可以很容易地檢查它們是否有相同的符號。

（你可以把它寫在foldr而言，如果你真的想 - 你可以在foldr方面寫groupBy，雖然標準的實施並不---它只是使事情變得更加複雜，你比他們需要。）

Answer 2

你可能想要你想要使用eg groupBy從Data.List。

import Data.List (groupBy) 
let result = groupBy (\ x y -> x*y>0) [1,2,3,-1,-2,-3,1,2,3] 

如果您不想單獨使用0例如，丹尼爾菲捨爾的sameSign函數，而不是檢查。

Answer 3

您想比較列表中每個數字的符號與其後繼符號。如果符號相同，則要將x放在與其後繼者相同的列表中，否則請啓動新的內部列表。

所以

combine x [[]] = [[x]] 
combine x wss@(yys@(y:_):zss) 
    | sameSign x y = (x:yys) : zss 
    | otherwise = [x] : wss 

會做你想要什麼（給出的sameSign實現）。但是這樣做效率不高（並且根本無法用於無限列表），因爲要知道使用哪個方程式，需要構建x之後的部分，這意味着必須首先達到輸入列表的末尾，然後必須退出列表。

的解決方案是懶惰，你必須檢查的第二個參數

combine x wss = (x:ssx) : rest 
    where 
    (ssx:rest) = case wss of 
        [[]] -> [] : [] 
        (yys@(y:ys) : zss) 
         | sameSign x y -> yys : zss 
         | otherwise -> [] : wss 

然後

foldr combine [[]] input 

之前開始構建其結果是你想要什麼，用，例如，

sameSign x y 
    | x < 0  = y < 0 
    | otherwise = y >= 0 

（當然，使用groupBy更短更容易，但是那樣做沒有使用foldr :)

Answer 4

我只是用foldr來提供可能的答案。我不是說你應該使用它，因爲它既不是非常高效（我使用a * b> = 0來顯示a和b是相同的符號），也不適用於無限列表。

combine = foldr f [] 
    where 
     f a [] = [[a]] 
     f a rest@((x:xs):ys) | x*a >= 0 = (a:x:xs):ys 
          | otherwise = [a]:rest 

Answer 5

我第二次使用groupBy來代替。不過，我想提出0在數學中不被視爲正數的觀點。迄今爲止還沒有其他答案提到過，類型類別的任何內容都必須實現signum，這將返回給定的號碼的符號。

import Data.List  (groupBy) 
import Data.Function (on) -- Can evade a lambda 

signGroup :: (Num a) => [a] -> [[a]] 
signGroup = groupBy ((==) `on` signum) 

用法示例：

> signGroup [1,2,3,0,0,-1,-2,1,2,0,3,4,-1] 
[[1,2,3],[0,0],[-1,-2],[1,2],[0],[3,4],[-1]] 

Answer 6

您在這裏需要稍微複雜的累加器：

data Sign = Neg | Zero | Pos 

signGroup :: [Integer] -> [[Integer]] 
signGroup xs = case 
    foldr 
    (\x (sign, ps, ns, ys) -> 
    -- x - current element 
    -- sign - sign of the prev. group 
    -- ps - positive numbers in the current group 
    -- ns - negative numbers in the current group 
    -- ys - final list 
    if x >= 0 
    then case sign of 
     Neg -> (Pos, x : ps, [], ns : ys) 
     Zero -> (Pos, x : ps, [], ys) 
     Pos -> (Pos, x : ps, [], ys) 
    else case sign of 
     Neg -> (Neg, [], x : ns, ys) 
     Zero -> (Neg, [], x : ns, ys) 
     Pos -> (Neg, [], x : ns, ps : ys)) 
    (Zero, [], [], []) 
    xs 
of 
    (_, [], [], ys) -> ys 
    (_, [], ns, ys) -> ns : ys 
    (_, ps, [], ys) -> ps : ys 
    (_, ps, ns, ys) -> ps : ns : ys -- <- unreachable 

-- signGroup [1,2,3,-1,-2,-3,1,2,3] 
-- => [[1,2,3],[-1,-2,-3],[1,2,3]]