list - 分割 Haskell 列表

Question

给定 haskell 中的排序列表，我如何获得分段列表，其中连续数字位于同一列表中。例如，如果我有一个排序列表 [1,2,3,4,7,8,10,12,13,15] 结果将是 [[1,2,3 ,4],[7,8],[10],[12,13],[15]]

Answer 1

这只是一个文件夹:

q :: (Enum a, Eq a) => [a] -> [[a]]
q = foldr foo []
  where
    foo x (ys@(y:_) : zzs) | succ x == y = (x:ys) : zzs
    foo x t = [x] : t

*Main> q [1,2,3,4,7,8,10,12,13,15]

[[1,2,3,4],[7,8],[10],[12,13],[15]]

更新:也可以变成foldl，这里我用“差异列表”来实现:

type N a = Maybe ( [[a]] -> [[a]], [a] -> [a], a )

p :: (Enum a, Eq a) => [a] -> [[a]]
p = close . foldl bar Nothing
  where
    close :: N a -> [[a]]
    close Nothing = []
    close (Just (f, g, _)) = (f  . (g []:)) []

    bar :: (Enum a, Eq a) => N a -> a -> N a
    bar Nothing x = Just (id, (x:), x)
    bar (Just (f, g, y)) x | succ y == x = Just (f, g . (x:), x)
                           | otherwise = Just ( f . (g []:), (x:), x)

更新 2:'f' 是在无限列表上安全的变体:

f :: (Enum a, Eq a) => [a] -> [[a]]
f [] = []
f (x:xs) = go x xs
  where
    go x xs = let (run, rest) = getRun x xs
              in run : f rest
    getRun x t@(y:ys) | succ x == y = let (run, rest) = getRun y ys
                                      in (x:run, rest)
    getRun x t = (x:[], t)

或更短的“f”:

f :: (Enum a, Eq a) => [a] -> [[a]]
f [] = []
f (x:xs) = getRun x xs
  where
    getRun x t@(y:ys) | succ x == y = let (run : rest) = getRun y ys
                                      in (x:run) : rest
    getRun x t = (x:[]) : f t

t3 = [1,2,3,10,11,12] ++ [15..]

*Main> take 3 (map (take 5) (f t3))

[[1,2,3],[10,11,12],[15,16,17,18,19]]