递归地将非连续列表排序为连续列表列表
最近我一直在尝试学习一些函数式编程(使用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风格！
回答 12
Stack Overflow用户
发布于 2011-02-18 09:22:58
在我的脑海中，最直接的方式是一个文件夹：
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通过将guard函数转换为参数，您可以对更多有趣的东西进行分组，而不仅仅是+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]]这个函数的实用程序是questionable...but fun！
Stack Overflow用户
发布于 2011-02-18 16:14:19
我不敢相信我得到了最短的解决方案。我知道这不是代码高尔夫，但我认为它仍然具有很好的可读性：
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..]顺便说一句，如果你更喜欢Data.List而不是GHC.Exts，groupWith snd可以用groupBy (\a b -> snd a == snd b)代替
编辑
顺便说一句:有没有比(curry $ (,) <$> ((-) <$> snd <*> fst) <*> snd)更好的方式来摆脱lambda (\a b -> (b-a, b))呢？
编辑2
是啊，我忘了(,)是个函数者。下面是模糊处理后的版本：
range = map (map fst) . groupWith snd . (flip $ zipWith $ curry $ fmap <$> (-).fst <*> id) [0..]欢迎提出建议。
Stack Overflow用户
发布于 2011-02-18 08:59:38
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使用有关列表的信息ping列表，然后对其执行操作(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是阿兹特克人的神，阿兹特克人的神是不能乱来的。
https://stackoverflow.com/questions/5036284
复制相似问题
腾讯云开发者
