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

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    

这可能是有点主观的,但我很想看到一个更好,更优雅,解决了这个在任何二郎或哈斯克尔(其他功能的语言太多,但我可能不明白.)否则,积分换刚刚杀青我蹩脚的新手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..]

或无点

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

[编辑]

顺便说一句:有没有比摆脱lambda 更好的方法？(\a b -> (b-a, b))(curry $ (,) <$> ((-) <$> snd <*> fst) <*> snd)

[编辑2]

是的,我忘了(,)是一个算子.所以这是混淆版本:

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

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