list - 如何将列表中的连续数字合并到Haskell的范围中？

我正竭尽全力围绕Haskell，并且很难确定该特定任务的一般过程/算法。我要做的基本上是给Haskell一个列表[1,2,3,5,6,9,16,17,18,19]并让它还给我[1-3、5、6、9、16 -19]，因此本质上会将三个或更多的连续数字转换为最低编号-最高编号样式的范围。我想我遇到的问题是与Haskell的功能范式作斗争的所有常见困难。因此，我将非常感谢通用算法或对如何从“Haskellian”的角度来看待这一点的见解。

提前致谢。

最佳答案

如果我正确理解了这个问题，那么我们的想法是将输入列表分成多个块，其中一个块可以是单个输入元素，也可以是至少三个连续元素的范围。

因此，让我们从定义用于表示此类块的数据类型开始:

data Chunk a = Single a | Range a a

如您所见，类型在输入元素的类型中是参数化的。

接下来，我们定义一个函数chunks，以根据输入元素列表实际构建一个块列表。为此，我们需要具有比较输入元素并获得给定输入元素(即其后继)的立即连续的能力。因此，该函数的类型为

chunks :: (Eq a, Enum a) => [a] -> [Chunk a]

实现相对简单:

chunks = foldr go []
 where
  go x (Single y : Single z : cs) | y == succ x && z == succ y = Range x z : cs
  go x (Range y z : cs) | y == succ x = Range x z : cs
  go x cs                             = Single x : cs

我们从右到左遍历该列表，并在运行时生成块。如果输入元素在其两个紧邻的连续元素之前(帮助函数go的第一种情况)或在以其紧邻的连续开始的范围之前(第二种情况)，我们将生成一个范围。否则，我们将生成一个元素(最后一种情况)。

为了安排漂亮的输出，我们将类型构造函数Chunk的应用程序声明为Show类的实例(假设输入元素的类型在Show中):

instance Show a => Show (Chunk a) where
  show (Single x ) = show x
  show (Range x y) = show x ++ "-" ++ show y

返回问题的示例，然后得到:

> chunks [1,2,3,5,6,9,16,17,18,19]
[1-3,5,6,9,16-19]

不幸的是，如果我们需要考虑有限元素类型，事情会稍微复杂一些。此类类型具有succ未定义的最大元素:

> chunks [maxBound, 1, 2, 3] :: [Chunk Int]
*** Exception: Prelude.Enum.succ{Int}: tried to take `succ' of maxBound

这表明我们应该从确定一个元素是否继另一个元素的特定方法中抽象出来:

chunksBy :: (a -> a -> Bool) -> [a] -> [Chunk a]
chunksBy succeeds = foldr go []
 where
  go x (Single y : Single z : cs) | y `succeeds` x && z `succeeds` y =
    Range x z : cs
  go x (Range y z : cs) | y `succeeds` x = Range x z : cs
  go x cs = Single x : cs

现在，上面给出的chunks版本可以通过简单地通过chunksBy来表示

chunks :: (Eq a, Enum a) => [a] -> [Chunk a]
chunks = chunksBy (\y x -> y == succ x)

而且，我们现在还可以为有界输入类型实现一个版本:

chunks' :: (Eq a, Enum a, Bounded a) => [a] -> [Chunk a]
chunks' = chunksBy (\y x -> x /= maxBound && y == succ x)

欢乐地带给我们:

> chunks' [maxBound, 1, 2, 3] :: [Chunk Int]
[9223372036854775807,1-3]