list - 如何将 Haskell 中的数字列表转换为范围列表？

Question

假设您有一个数字列表，[1,2,3,5,6,7,8,9,11,12,15,16,17]

并且您想要一个将其作为输入并返回类似内容的函数

[[1,3],[5,9],[11,12],[15,17]] 或者也许[(1,3)、(5,9)、(11,12)、(15,17)]

这将如何完成？我在网上找到的所有解决方案都非常非常长而且非常复杂，而对于像 haskell 这样的函数式语言来说这似乎是一个简单的问题

Answer 1

所以我们有一个数字列表，

xs = [1,2,3,5,6,7,8,9,11,12,14,16,17]     -- 14 sic!

我们把它变成一个段列表，

ys = [[x,x+1] | x <- xs]
  -- [[1,2], [2,3], [3,4], [5,6], ..., [11,12], [12,13], [14,15], [16,17], [17,18] ]

我们加入感人的片段，

zs = foldr g [] ys
  -- [[1,4], [5,10], [11,13], [14,15], [16,18]]
  where
  g [a,b] []                  =  [[a,b]]
  g [a,b] r@([c,d]:t) | b==c  =  [a,d]:t
                 | otherwise  =  [a,b]:r

然后我们从每个段的结束值中减去1，

ws = [[a,b-1] | [a,b] <- zs]
  -- [[1,3], [5,9], [11,12], [14,14], [16,17]]

总而言之，我们得到了

ranges :: (Num t, Eq t) => [t] -> [[t]]
ranges  =  map (\[a,b] -> [a,b-1]) . foldr g [] . map (\x -> [x,x+1]) 
  where
  g [a,b] []                  =  [[a,b]]
  g [a,b] r@([c,d]:t) | b==c  =  [a,d]:t
                 | otherwise  =  [a,b]:r

简单明了。

编辑:或者，适本地偷懒，

  where
  g [a,b] r = [a,x]:y
       where
       (x,y) = case r of ([c,d]:t) | b==c  -> (d,t)   -- delay forcing
                         _                 -> (b,r)

更新:为 dfeuer注意，(a,a) 类型比 [a,a] 更好。在此代码中凡出现 [P,Q] 的地方，请将其替换为 (P,Q)。这将改进代码，并且可读性成本为零。