将列表分成子列表：相同的值被添加到一个子列表，不同的值被添加到另一个

Question

将列表划分为子列表：将相同的值添加到一个子列表，将不同的值添加到另一个子列表。它需要通过列表的一次传递使用 foldr 来完成，而不是使用 ++.

例如：

ghci> splitList [1,2,2,4,5,7,7,8,9] 

[[1],[2,2],[4,5],[7,7],[8,9]]

我做了类似的事情：

splitList :: [Int] -> [[Int]]
splitList = getRes . foldr func5 ([],False,0) where
  func5 c ([],_,_) = ([[c]],False,c)
  func5 c (y@(x:xs), b, l) | c == l = ((c:x):xs, False, c)
                           | b = ((c:x):xs, False, c)
                           | otherwise = ([c]:y, True, c)

getRes :: ([[Int]], Bool, Int) -> [[Int]]
getRes (a,_,_) = a

但它并没有像我预期的那样工作...

ghci> splitList [1,2,2,4,5,7,7,8,9]

[[1],[2,2],[4,5],[7,7,8],[9]]

Answer 1

由于您正在使用 foldr，

> splitList [1,2,2,4,5,7,7,8,9]

[[1],[2,2],[4,5],[7,7],[8,9]]

应该像

一样从右边开始工作

> splitList [1,2,2,4,5,7,7,8,9]
                              []
                           [[9]]
                         [[8,9]]
                       [[7,8,9]]
                     [[7,7],[8,9]]
                   [[5],[7,7],[8,9]]
                 [[4,5],[7,7],[8,9]]
               [[2,4,5],[7,7],[8,9]]
             [[2,2],[4,5],[7,7],[8,9]]
           [[1],[2,2],[4,5],[7,7],[8,9]]

现在剩下的就是用代码写下来了。

从上面可以看出，我们只需要将当前元素与“累加器”的头部进行比较（特殊情况除外，列表的最后两个元素是无条件收集的），同时保持“相同性”旗帜。所以可以编码为

splitList :: Eq a => [a] -> [[a]]
splitList xs = snd $ foldr g (undefined,[]) xs
  where
  g x (b,[]) = (b,[[x]])
  g x (_,[y]:t) = (x==y,[x,y]:t)
  g x (b,(a:r):t)
     | (x==a)==b  = (b,(x:a:r):t)
     | otherwise  = (not b, if b then [x]:(a:r):t
                                 else [x,a]:r:t)

测试：

> splitList [1,2,2,4,5,7,7,8,9]
[[1],[2,2],[4,5],[7,7],[8,9]]

> splitList [1,2,2,4,5,7,7,8,9,9]
[[1],[2,2],[4,5],[7,7],[8],[9,9]]

> splitList [1,2,2,4,5,7,8,9,9,9]
[[1],[2,2],[4,5,7,8],[9,9,9]]

将列表分成子列表：相同的值被添加到一个子列表，不同的值被添加到另一个

Divide the list into sub-lists: the same values are added to one sublist and different values are added to another

list

haskell

fold