Как объединить последовательные числа в списке в диапазон Haskell?

Question

Я пытаюсь схватиться за Haskell, и мне трудно определить общую процедуру / алгоритм для этой конкретной c задачи. Я просто хочу дать Haskell список [1,2,3,5,6,9,16,17,18,19] и вернуть мне [1-3, 5, 6, 9 , 16-19], так что по сути превращение трех или более последовательных чисел в диапазон в стиле наименьшее число - наибольшее число. Что у меня есть проблема с этим, я полагаю, это слишком распространенные трудности, связанные с функциональной парадигмой Haskell. Так что я был бы очень признателен за общий алгоритм или понимание того, как рассматривать это с «хаскелевской» точки зрения.

Заранее спасибо.

Answer 1

Если я правильно понял вопрос, идея состоит в том, чтобы разбить входные списки на блоки, где блок - это либо один входной элемент, либо диапазон, по крайней мере, из трех последовательных элементов.

Итак, давайте начнем с определения типа данных для представления таких фрагментов:

data Chunk a = Single a | Range a a

Как видите, тип - параметр c в типе входных элементов.

Затем мы определяем функцию 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. Мы генерируем диапазон, если входной элемент предшествует двум своим непосредственным последовательным элементам (первый случай вспомогательной функции 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

Это предполагает, что мы должны абстрагироваться от специфического c подхода для определения, следует ли один элемент за другим:

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]

Answer 2

Используйте рекурсию . Рекурсия - это прыжок веры. Предполагается, что вы уже написали свое определение и поэтому можете ( «рекурсивно» ) вызвать it для подзадачи вашей полной проблемы и объединить (рекурсивно вычисленную) подзадачу -результат с оставшейся частью, чтобы получить полное решение - easy :

ranges xs  =  let  (leftovers, subproblem) = split xs
                   subresult = ranges subproblem
                   result = combine leftovers subresult
              in
                   result
   where
   split xs  =  ....
   combine as rs  =  ....

Теперь мы знаем тип rs в combine (т.е. subresult in ranges) - это то, что возвращает ranges:

ranges :: [a] -> rngs

Итак, как нам split наш список ввода xs? Философия типо-ориентированного дизайна гласит: следует за типом .

xs - это список [a] из a s. У этого типа два случая: [] или x:ys с x :: a и ys :: [a]. Таким образом, самый простой способ разбить список на меньший список и некоторую оставшуюся часть:

    split (x:xs)  =  (x, ys)
    split []      =  *error* "no way to do this"   -- intentionally invalid code

Принимая во внимание последний случай, нам придется настроить общий дизайн, чтобы учесть это. Но обо всем по порядку, что может быть за тип rngs? Исходя из данных вашего примера, это список rng s, естественно, rngs ~ [rng].

Тип rng, хотя у нас есть значительная степень свободы, чтобы сделать его тем, что мы хотим. Случаи, которые мы должны учитывать, - это пары и одиночки:

data Rng a  =  Single a 
            |  Pair a a

.... и теперь нам нужно совместить неровные части вместе в одну картинку.

Сочетание числа с диапазоном, начинающимся с порядкового номера, очевидно.

Объединение числа с одним будет иметь два очевидных случая, независимо от того, являются ли эти числа последовательными или нет.

Я думаю / надеюсь, что вы можете продолжить отсюда.

Answer 3

Во-первых, все элементы списка должны быть одного типа. Ваш результирующий список имеет два разных типа. Range s (что бы это ни значило) и Int s. Мы должны преобразовать один единственный di git в диапазон, где наименьшее и наибольшее значение совпадают.

Как уже было сказано, вы должны определить тип данных Range и свернуть свой список Int в список Range

data Range = Range {from :: Int , to :: Int}

intsToRange :: [Int] -> [Range]
intsToRange [] = []
intsToRange [x] = [Range x x]
intsToRange (x:y:xs) = ...  -- hint: you can use and auxiliar acc which holds the lowest value and keep recursion till find a y - x differece greater than 1.

Вы также можете использовать fold , et c ... чтобы получить очень точную точку зрения