compress :: [Int] -> [[Int]]
compress (x:xs) = let (y,ys) = walk x xs
in [x,y]:compress ys
where walk :: Int -> [Int] -> (Int,[Int])
walk c v@(y:ys) = let (z,zs) = walk y ys
in if y == c + 1 then
(z + 1,zs)
else
(1,v)
walk c [] = (1,[])
compress [] = []
Refactorings
No refactoring yet !
bob
April 15, 2009, April 15, 2009 17:12, permalink
By the way your problem is very similar to the "look and say sequence" [http://en.wikipedia.org/wiki/Look_and_say_sequence], except that you don't concatenate the groups, and that your element and count are listed in the opposite order.
import Data.List (group) compress :: [Int] -> [[Int]] compress = map (\g -> [head g, length g]) . group
sargon
April 15, 2009, April 15, 2009 17:48, permalink
"look and say sequence" has some flavour of "the game of life" but more abstract.
Yeah the damn map function, when will I finally use it first, but your solution dosn't behave like my example.
compress $ concat [[1..4],[6..8]]
My: [[1,4],[6,3]]
Your: [[1,1],[2,1],[3,1],[4,1],[6,1],[7,1],[8,1]]
But thanks for remind me of map,fold(r,l) ... this should do it better
compress :: [Int] -> [(Int,Int)] compress (l:ls) = reverse $ foldl (\ o@((c,i):cs) x -> if x == c + i then (c,i+1):cs else (x,1):o) [(l,1)] ls compress [] = []
Alec Leitner
April 15, 2009, April 15, 2009 18:37, permalink
Oh, I might have to learn Haskell to optimize my Ruby code.
Plus I just realized that the problem basically is about how to convert an array to range objects (and back again), which is much easier to explain than how I tried it. Now I can only hope someone can come up with a ruby solution. :)
bob
April 15, 2009, April 15, 2009 20:40, permalink
oops i didn't read the original problem so misunderstood what it was supposed to do; i thought it was something different
how about something like this:
import Data.List (group, mapAccumL) compress :: [Int] -> [[Int]] compress = snd . mapAccumL (\z g -> (z + length g, [z + head g, length g])) 0 . group . zipWith (flip (-)) [0..]
sargon
April 16, 2009, April 16, 2009 06:08, permalink
_geil_
Took a moment before I did completely understand what your code do, nice idea.
Kim Burgestrand
October 21, 2009, October 21, 2009 04:58, permalink
I realize this is old, but I found it and figured I'd have a go.
# Imports [haskell]
import Data.List (groupBy)
import Control.Arrow ((&&&))
# Function [haskell]
compress :: (Num a, Enum a) => [a] -> [(a, Int)]
compress = map (snd . head &&& length) . groupBy f . zip [1..]
where f (i, x) (i', x') = i' - i == x' - x
I took the idea from "Alec Leitner" (here: http://assets.refactormycode.com/codes/822-compressing-an-array-of-integers)
and ported it into Haskell, because Haskell is type save the result of compress [1,3,5] would be [[1,1],[3,1],[5,1]],
see any tricks to get this smarter ?