Рекурсивно сортировать несмежные списки в список смежных списков

Question

В последнее время я пытался немного изучить функциональное программирование (с помощью Haskell & Erlang), и меня всегда поражали краткие решения, которые люди могут придумать, когда они могут рекурсивно мыслить и знать инструменты.

Я хочу, чтобы функция преобразовывала список отсортированных, уникальных, несмежных целых чисел в список смежных списков, т.е.:

[1,2,3,6,7,8,10,11]

до:

[[1,2,3], [6,7,8], [10,11]

Это было лучшее, что я мог придумать в Haskell (две функции) ::

make_ranges :: [[Int]] -> [Int] -> [[Int]]
make_ranges ranges [] = ranges
make_ranges [] (x:xs)
    | null xs = [[x]]
    | otherwise = make_ranges [[x]] xs
make_ranges ranges (x:xs)
    | (last (last ranges)) + 1 == x =
        make_ranges ((init ranges) ++ [(last ranges ++ [x])]) xs
    | otherwise = make_ranges (ranges ++ [[x]]) xs

rangify :: [Int] -> [[Int]]
rangify lst = make_ranges [] lst    

Это может быть немного субъективно, но мне было бы интересно увидеть лучшее, более изящное, решение этого на Erlang или Haskell (также на других функциональных языках, но я не могу этого понять). В противном случае, пункты для простого исправления стиль моего дерьмового новичка в Haskell!

Answer 1

Самый простой способ в моей голове - это фолд:

ranges = foldr step []
    where step x [] = [[x]]
          step x acc@((y:ys):zs) | y == x + 1 = (x:y:ys):zs
                                 | otherwise  = [x]:acc

Или, более кратко:

ranges = foldr step []
    where step x ((y:ys):zs) | y == x + 1 = (x:y:ys):zs
          step x acc = [x]:acc

Но подождите, это еще не все!

abstractRanges f = foldr step []
    where step x ((y:ys):zs) | f x y = (x:y:ys):zs
          step x acc = [x]:acc

ranges = abstractRanges (\x y -> y == x + 1)
powerRanges = abstractRanges (\x y -> y == x*x) -- mighty morphin

Превратив функцию защиты в параметр, вы можете сгруппировать более интересные вещи, чем просто +1 последовательность.

*Main> powerRanges [1,1,1,2,4,16,3,9,81,5,25]
[[1,1,1],[2,4,16],[3,9,81],[5,25]]

Полезность этой конкретной функции сомнительна ... но весело!

Answer 2

Не могу поверить, что нашел самое короткое решение. Я знаю, что это не код гольф, но я думаю, что это все еще вполне читабельно:

import GHC.Exts
range xs = map (map fst) $ groupWith snd $ zipWith (\a b -> (a, a-b)) xs [0..]

или pointfree

range = map (map snd) . groupWith fst . zipWith (\a b -> (b-a, b)) [0..]

Кстати, groupWith snd можно заменить на groupBy (\a b -> snd a == snd b), если вы предпочитаете Data.List вместо GHC.Exts

[Изменить]

Кстати: есть ли приятнее способ избавиться от лямбды (\a b -> (b-a, b)), чем (curry $ (,) <$> ((-) <$> snd <*> fst) <*> snd)?

[Изменить 2]

Да, я забыл (,) - функтор. Итак, вот запутанная версия:

range = map (map fst) . groupWith snd . (flip $ zipWith $ curry $ fmap <$> (-).fst <*> id) [0..]

Предложения приветствуются ...

Answer 3

Другая версия на Erlang:

part(List) -> part(List,[]).
part([H1,H2|T],Acc) when H1 =:= H2 - 1 -> 
    part([H2|T],[H1|Acc]);
part([H1|T],Acc) ->
    [lists:reverse([H1|Acc]) | part(T,[])];
part([],Acc) -> Acc.

Answer 4

import Data.List (groupBy)

ranges xs = (map.map) snd 
          . groupBy (const fst) 
          . zip (True : zipWith ((==) . succ) xs (tail xs))
          $ xs

Что касается того, как придумать такую ​​вещь: я начал с zipWith f xs (tail xs), который является обычной идиомой, когда вы хотите что-то сделать с последовательными элементами списка.Аналогичным образом zip проверяет список с информацией о списке, а затем воздействует на него (groupBy).Остальное - сантехника.

Тогда, конечно, вы можете кормить его через @pl и получить:

import Data.List (groupBy)
import Control.Monad (ap)
import Control.Monad.Instances()

ranges = (((map.map) snd) 
           . groupBy (const fst)) 
         .) =<< zip 
         . (True:) 
         . ((zipWith ((==) . succ)) `ap` tail)

, что, по моему авторитетному определению, является злом из-за Mondad ((->) a), Дважды , даже.Поток данных слишком извилистый, чтобы его можно было каким-либо разумным образом изложить.zipaptail - ацтекский бог, и с ацтекскими богами не следует путаться.

Answer 5

Эрланг с использованием Foldr:

ranges(List) ->
    lists:foldr(fun (X, [[Y | Ys], Acc]) when Y == X + 1 ->
                        [[X, Y | Ys], Acc];
                    (X, Acc) ->
                        [[X] | Acc]
                end, [], List).

Answer 6

k z = map (fst <$>) . groupBy (const snd) . 
        zip z . (False:) . (zipWith ((==) . succ) <*> tail) $ z

Answer 7

Попробуйте повторно использовать стандартные функции.

import Data.List (groupBy)

rangeify :: (Num a) => [a] -> [[a]]
rangeify l = map (map fst) $ groupBy (const snd) $ zip l contigPoints
  where contigPoints = False : zipWith (==) (map (+1) l) (drop 1 l)

---

Или, следуя (смешанному) совету использовать unfoldr, прекратите злоупотреблять groupBy и будьте счастливы использовать частичные функции, когда это не такдело:

import Control.Arrow ((***))
import Data.List (unfoldr)

spanContig :: (Num a) => [a] -> [[a]]
spanContig l =
    map fst *** map fst $ span (\(a, b) -> a == b + 1) $ zip l (head l - 1 : l)

rangeify :: (Num a) => [a] -> [[a]]
rangeify = unfoldr $ \l -> if null l then Nothing else Just $ spanContig l

Answer 8

Стандартной схемы рекурсии параморфизма нет в модуле Data.List на Haskell, хотя я думаю, что так и должно быть.Вот решение, использующее параморфизм, поскольку вы строите список списков из списка, его использование немного обманчиво:

contig :: (Eq a, Num a) => [a] -> [[a]]
contig = para phi [] where
  phi x ((y:_),(a:acc)) | x + 1 == y = (x:a):acc
  phi x (_,       acc)               = [x]:acc

Параморфизм - это общая рекурсия или сгиб с Lookahead :

para :: (a -> ([a], b) -> b) -> b -> [a] -> b
para phi b []     = b
para phi b (x:xs) = phi x (xs, para phi b xs)

Answer 9

Это может быть довольно ясно и просто в Эрланге:

partition([]) -> [];
partition([A|T]) -> partition(T, [A]).

partition([A|T], [B|_]=R) when A =:= B+1 -> partition(T, [A|R]);
partition(L, P) -> [lists:reverse(P)|partition(L)].

Редактировать : Просто для любопытства я сравнил свои и Лукас х версия и моя, кажется, примерно на 10% быстрее либо в нативном, либо в версии с байт-кодом при тестировании, что я сгенерировал lists:usort([random:uniform(1000000)||_<-lists:seq(1,1000000)]) на версии R14B01 64b на моем ноутбуке.(Набор для тестирования имеет длину 669462 и был разделен на 232451 подсписков.)

Edit2 : Другие данные теста lists:usort([random:uniform(1000000)||_<-lists:seq(1,10000000)]), длина 999963 и 38 разделов, значительно отличаются от собственного кода.Моя версия заканчивается менее чем за половину времени.Версия байт-кода работает примерно на 20% быстрее.

Edit3 : некоторые микрооптимизации, которые обеспечивают дополнительную производительность, но приводят к более уродливому и менее обслуживаемому коду:

part4([]) -> [];
part4([A|T]) -> part4(T, A, []).

part4([A|T], B, R) when A =:= B+1 -> part4(T, A, [B|R]);
part4([A|T], B, []) -> [[B]|part4(T, A, [])];
part4([A|T], B, R) -> [lists:reverse(R, [B])|part4(T, A, [])];
part4([], B, R) -> [lists:reverse(R,[B])].

Answer 10

Для сравнения приведу реализацию на Erlang:

partition(L)  -> [lists:reverse(T) || T <- lists:reverse(partition(L, {[], []}))].

partition([E|L], {R, [EL|_] = T}) when E == EL + 1 -> partition(L, {R, [E|T]});
partition([E|L], {R, []})                          -> partition(L, {R, [E]});
partition([E|L], {R, T})                           -> partition(L, {[T|R], [E]});
partition([],    {R, []})                          -> R;
partition([],    {R, T})                           -> [T|R].