haskell - Recursively sort non-contiguous list to list of contiguous lists -
i've been trying learn bit of functional programming (with haskell & erlang) lately , i'm amazed @ succinct solutions people can come when can think recursively , know tools.
i want function convert list of sorted, unique, non-contiguous integers list of contiguous lists, i.e:
[1,2,3,6,7,8,10,11]
to:
[[1,2,3], [6,7,8], [10,11]
this best come in haskell (two functions)::
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
it might bit subjective i'd interested see better, more elegant, solution in either erlang or haskell (other functional languages might not understand it.) otherwise, points fixing crappy beginner's haskell style!
most straightforward way in mind foldr:
ranges = foldr step [] step x [] = [[x]] step x acc@((y:ys):zs) | y == x + 1 = (x:y:ys):zs | otherwise = [x]:acc
or, more concisely:
ranges = foldr step [] step x ((y:ys):zs) | y == x + 1 = (x:y:ys):zs step x acc = [x]:acc
but wait, there's more!
abstractranges f = foldr step [] 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
by turning guard function parameter, can group more interesting things +1 sequences.
*main> powerranges [1,1,1,2,4,16,3,9,81,5,25] [[1,1,1],[2,4,16],[3,9,81],[5,25]]
the utility of particular function questionable...but fun!
Comments
Post a Comment