将非连续列表递归排序为连续列表的列表

Question

最近我一直在尝试学习一些函数式编程（使用 Haskell 和 Erlang），我总是对人们在能够递归思考并了解工具时能够想出的简洁解决方案感到惊讶。

我想要一个函数将排序的、唯一的、非连续整数的列表转换为连续列表的列表，即：

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

to：

[[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

在我看来，最直接的方法是foldr：

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..]

BTW，groupWith snd 可以替换为 groupBy (\ab -> snd a == snd b ) 如果您更喜欢 Data.List 而不是 GHC.Exts

[编辑]

顺便说一句：有没有更好的(\ab -> (ba, b)) 的方法比 (curry $ (,) <$> ((-) <$ > snd <*> fst) <*> snd) ？

[编辑 2]

是的，我忘记了 (,) 是一个函子。所以这是混淆版本：

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

欢迎提出建议......

Answer 3

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 和 get: 提供它

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 4

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 5

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

Answer 6

尝试重用标准函数。

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 7

Erlang 使用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 8

这是我的 v0.1，我可能可以让它变得更好：

makeCont :: [Int] -> [[Int]]
makeCont [] = []
makeCont [a] = [[a]]
makeCont (a:b:xs) = if b - a == 1
                        then (a : head next) : tail next
                        else [a] : next
                    where
                        next :: [[Int]]
                        next = makeCont (b:xs)

我会尽力让它变得更好。我想编辑即将到来。

Answer 9

作为比较，下面是 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].

Answer 10

标准的同态递归方案不在 Haskell 的 Data.List 模块中，尽管我认为它应该是。这是使用同态的解决方案，因为您正在从列表构建列表列表，所以缺点有点棘手：

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

同态是一般递归或带有前瞻的折叠：

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 11

在 Erlang 中它可以非常清晰和简单：

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)].

编辑：出于好奇，我比较了我的和 Lukas< /a> 的版本 和我的在测试集上的本地或字节码版本中似乎快了大约 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 12

这是一个 haskell 菜鸟的尝试

ranges ls = let (a, r) = foldl (\(r, a@(h:t)) e -> if h + 1 == e then (r, e:a) else (a:r, [e])) ([], [head ls]) (tail ls)
            in           reverse . map reverse $ r : a