0

给定一个负数和正数序列的列表，如何使用 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 ) [[]]

这是错误的

非常感谢您提前提供的帮助。

4

6 回答 6

5

我支持的用法groupBy。但是，我想提出一点，即 0 在数学中不被视为正数。并且到目前为止没有其他答案提到，任何属于类型类的东西都Num必须实现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]]
于 2012-10-11T16:28:23.243 回答
2

您想将列表中每个数字的符号与其后继数字的符号进行比较。如果符号相同，则要放入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:)

于 2012-10-11T11:52:36.020 回答
1

你需要一个稍微复杂一点的累加器：

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]]
于 2012-10-12T23:18:54.363 回答
0

我将使用 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
于 2012-10-11T13:38:51.533 回答
0

使用最好的工具来完成这项工作。在这种情况下，最适合这项工作的工具是groupBy.

groupBy将列表的两个成员传递给您的函数，因此您可以轻松检查它们是否具有相同的符号。

（foldr如果你真的想写的话，你可以用 --- 你groupBy可以foldr用

于 2012-10-11T11:52:06.027 回答
0

groupBy您可以使用例如from得到想要的结果Data.List。

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

如果您不想0单独处理，请使用例如 Daniel Fischer 的sameSign函数来代替检查。

于 2012-10-11T11:52:24.400 回答