在Haskell中将列表拆分为非空子列表 [英] Split a list into non-empty sub-lists in Haskell

问题描述

我必须将给定列表分为非空子列表，每个子列表 严格按升序，严格降序或包含所有相等的元素.例如，[5,6,7,2,1,1,1]应该变为[[5,6,7]，[2,1]，[1,1]].

I have to split the given list into non-empty sub-lists each of which is either in strictly ascending order, in strictly descending order, or contains all equal elements. For example, [5,6,7,2,1,1,1] should become [[5,6,7],[2,1],[1,1]].

这是我到目前为止所做的:

Here is what I have done so far:

splitSort :: Ord a => [a] -> [[a]] 
splitSort ns = foldr k [] ns
  where
    k a []  = [[a]]
    k a ns'@(y:ys) | a <= head y = (a:y):ys
                   | otherwise = [a]:ns'

我认为我已经很接近了，但是当我使用它时，它会输出[[5,6,7]，[2]，[1,1,1]]而不是[[5,6,7]，[2 ，1]，[1,1]].

I think I am quite close but when I use it it outputs [[5,6,7],[2],[1,1,1]] instead of [[5,6,7],[2,1],[1,1]].

推荐答案

最初的尝试原来很长，可能效率很低，但是为了完整起见，我将其保留为罢工.最好只是跳到最后寻找答案.

The initial try turned out to be lengthy probably inefficient but i will keep it striked for the sake of integrity with the comments. You best just skip to the end for the answer.

很好的问题...但是事实证明是一点点硬糖.我的方法是细分的，我将逐一解释；

Nice question... but turns out to be a little hard candy. My approach is in segments, those of each i will explain;

import Data.List (groupBy)

splitSort :: Ord a => [a] -> [[a]]
splitSort (x:xs) = (:) <$> (x :) . head <*> tail $ interim
                   where
                   pattern = zipWith compare <$> init <*> tail
                   tuples  = zipWith (,) <$> tail <*> pattern
                   groups  = groupBy (\p c -> snd p == snd c) . tuples $ (x:xs)
                   interim = groups >>= return . map fst

*Main> splitSort [5,6,7,2,1,1,1]
[[5,6,7],[2,1],[1,1]]

• pattern函数(zipWith compare <$> init <*> tail)的类型为Ord a => [a] -> [Ordering]，当与[5,6,7,2,1,1,1]一起使用时，将其init与它的tail和zipWith进行比较.因此结果将是[LT,LT,GT,GT,EQ,EQ].这就是我们需要的模式.
• tuples函数将采用列表中的tail，并将其元素与pattern结果中的相应元素进行元组化.所以我们最终会得到类似[(6,LT),(7,LT),(2,GT),(1,GT),(1,EQ),(1,EQ)]的东西.
• groups函数使用 Data.List.groupBy 在元组的第二项上，并生成所需的子列表，例如[[(6,LT),(7,LT)],[(2,GT),(1,GT)],[(1,EQ),(1,EQ)]]
• 临时是我们单调摆脱Ordering类型值和元组的地方.临时结果为[[6,7],[2,1],[1,1]].
• 最后，在主函数主体(:) <$> (x :) . head <*> tail $ interim中，将列表的第一项(x)附加到head的子列表中(无论如何，都必须存在)并荣耀地提出了解决方案.
• The pattern function (zipWith compare <$> init <*> tail) is of type Ord a => [a] -> [Ordering] when fed with [5,6,7,2,1,1,1] compares the init of it by the tail of it by zipWith. So the result would be [LT,LT,GT,GT,EQ,EQ]. This is the pattern we need.
• The tuples function will take the tail of our list and will tuple up it's elements with the corresponding elements from the result of pattern. So we will end up with something like [(6,LT),(7,LT),(2,GT),(1,GT),(1,EQ),(1,EQ)].
• The groups function utilizes Data.List.groupBy over the second items of the tuples and generates the required sublists such as [[(6,LT),(7,LT)],[(2,GT),(1,GT)],[(1,EQ),(1,EQ)]]
• Interim is where we monadically get rid of the Ordering type values and tuples. The result of interim is [[6,7],[2,1],[1,1]].
• Finally at the main function body (:) <$> (x :) . head <*> tail $ interim appends the first item of our list (x) to the sublist at head (it has to be there whatever the case) and gloriously present the solution.

因此，调查@JonasDuregård发现的[0,1,0,1]导致的[[0,1],[0],[1]]问题，我们可以得出结论，除了单挑时的最后一个.我的意思是对于像[0,1,0,1,0,1,0]这样的输入，上面的代码会生成[[0,1],[0],[1],[0],[1],[0]]，而它应该是[[0,1],[0,1],[0,1],[0]].因此，我相信在最后阶段添加squeeze函数应该可以纠正逻辑.

So investigating the [0,1,0,1] resulting [[0,1],[0],[1]] problem that @Jonas Duregård discovered, we can conclude that in the result there shall be no sub lists with a length of 1 except for the last one when singled out. I mean for an input like [0,1,0,1,0,1,0] the above code produces [[0,1],[0],[1],[0],[1],[0]] while it should [[0,1],[0,1],[0,1],[0]]. So I believe adding a squeeze function at the very last stage should correct the logic.

import Data.List (groupBy)

splitSort :: Ord a => [a] -> [[a]]
splitSort []     = []
splitSort [x]    = [[x]]
splitSort (x:xs) = squeeze $ (:) <$> (x :) . head <*> tail $ interim
                   where
                   pattern = zipWith compare <$> init <*> tail
                   tuples  = zipWith (,) <$> tail <*> pattern
                   groups  = groupBy (\p c -> snd p == snd c) $ tuples (x:xs)
                   interim = groups >>= return . map fst

                   squeeze []           = []
                   squeeze [y]          = [y]
                   squeeze ([n]:[m]:ys) = [n,m] : squeeze ys
                   squeeze ([n]:(m1:m2:ms):ys) | compare n m1 == compare m1 m2 = (n:m1:m2:ms) : squeeze ys
                                               | otherwise                     = [n] : (m1:m2:ms) : squeeze ys
                   squeeze (y:ys)       = y : squeeze s

*Main> splitSort [0,1, 0, 1, 0, 1, 0]
[[0,1],[0,1],[0,1],[0]]
*Main> splitSort [5,6,7,2,1,1,1]
[[5,6,7],[2,1],[1,1]]
*Main> splitSort [0,0,1,0,-1]
[[0,0],[1,0,-1]]

是；您也将同意，该代码原来太冗长，而且可能效率不高.

Yes; as you will also agree the code has turned out to be a little too lengthy and possibly not so efficient.

答案:当我不断告诉我自己走错路时，我必须相信我的后脑.有时，像在这种情况下，问题被简化为一条if then else指令，比我最初预期的要简单得多.

The Answer: I have to trust the back of my head when it keeps telling me i am not on the right track. Sometimes, like in this case, the problem reduces down to a single if then else instruction, much simpler than i had initially anticipated.

runner :: Ord a => Maybe Ordering -> [a] -> [[a]]
runner _       []  = []
runner _       [p] = [[p]]
runner mo (p:q:rs) = let mo'    = Just (compare p q)
                         (s:ss) = runner mo' (q:rs)
                     in if mo == mo' || mo == Nothing then (p:s):ss
                                                      else [p] : runner Nothing (q:rs)
splitSort :: Ord a => [a] -> [[a]]
splitSort = runner Nothing

我的测试用例

*Main> splitSort [0,1, 0, 1, 0, 1, 0]
[[0,1],[0,1],[0,1],[0]]
*Main> splitSort [5,6,7,2,1,1,1]
[[5,6,7],[2,1],[1,1]]
*Main> splitSort [0,0,1,0,-1]
[[0,0],[1,0,-1]]
*Main> splitSort [1,2,3,5,2,0,0,0,-1,-1,0]
[[1,2,3,5],[2,0],[0,0],[-1,-1],[0]]

这篇关于在Haskell中将列表拆分为非空子列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！