Extract logic applied in a sequence of integers

Question

I've done it in C# before but thought that a functional language would be a good fit for this kind of thing.

From this ascending list of integers:

[100,103,106,112,118,121]

I had to calculate the difference between two consecutive numbers and group them while the result doesn't change. The final output must be a string like this:

"(group.length x difference)+(next group.length + next diff)+.."

Note that a same difference can appear multiple times in the sequence if it's not consecutive.

For this sample: "2x3+2x6+1x3"

import Data.List
countDelta :: [[a]] -> [(Int,a)]
countDelta [] = []
countDelta [[]] = []
countDelta ( (y:zs) : (bs) ) = (length zs + 1, y) : countDelta bs
groupByDelta :: [Int] -> [(Int,Int)]
groupByDelta (xs) = countDelta ( group [b-a | (a:b:_) <- tails xs] )
printTuples :: [(Int, Int)] -> String
printTuples [] = ""
printTuples [(x,y)] = show x ++ "x" ++ show y
printTuples (x:xs) = printTuples [x] ++ "+" ++ printTuples xs
getSequenceLogic :: [Int] -> String
getSequenceLogic [] = ""
getSequenceLogic [x] = printTuples [(1,0)]
getSequenceLogic (xs) = printTuples (groupByDelta xs)

Sample call:

getSequenceLogic [100,103,106,112,118,121]

I get the expected result but is there any obvious error?

• wei2912: What's the expected output for a single element list?
• Stéphane Bebrone: I've made the choice to print "1x0" in this case.

Answer 1

I managed to simplify a pair of your functions:

countDelta

countDelta = map (\(x:xs) -> (length xs + 1, x))

In fact most of the logic in your countDelta was just reinventing map, so actually using map makes it much easier.

ShowTuples

(You named it printTuples but it does not print the tuples, printing to the screen is an action, while this function is pure, so I named it showTuples as show is conventionally used in Haskell when a String is the output)

import Data.List
showTuples = intercalate "+" . map (\(x, y) -> (show x ++ "x" ++ show y))

Here you were just putting "x" in between the two elements of each tuple and "+" in between the tuples. Half of the code was reinventing map, the other half intercalate using these built-ins makes the code much shorter and self-explanatory.

getSequenceLogic

A minor simplification only here: you can drop the [] case as the xs case already handles it correctly:

getSequenceLogic [x] = showTuples [(1,0)]
getSequenceLogic xs = showTuples (groupByDelta xs)

• Caridorc: Also: countDelta = map (length &&& head) but that is more advanced using Control.Arrow so I did not include that in the answer. Still note how nicely it expresses that we want a tuple containing the length of the list first, the head second.

Answer 2

I'm not convinced that your special case

getSequenceLogic [x] = printTuples [(1,0)]

is justified. If [100, 103] is to be summarized as "1x3", then don't think that [100] should be "1x0". I would consider an empty string to be a reasonable summary of [100].

---

When possible, you want to avoid explicit recursion in favour of higher-level operations. A solution like this is much more compact:

import Data.List (group, intercalate)
diffSummary :: Num a => Eq a => Show a => [a] -> String
diffSummary xs = intercalate "+" $ map text groups
 where
 deltas = map (uncurry (-)) $ zip (tail xs) xs
 groups = map (\g -> (length g, head g)) $ group deltas
 text (len, num) = show len ++ "x" ++ show num

Let's start with the type signature. I suggest avoiding names like "get...", since you can assume that immutability applies everywhere in Haskell. Also, you can generalize the input type to Integral a (normal Ints and big Integers) for free. In fact, the same logic applies to any type that you can subtract, compare for equality, and represent as a string.

Similarly, printTuples is misnamed, as it's not actually printing; it's just producing a string representation. In any case, the function would be better implemented using Data.List.intercalate.

groupDelta is a bit hairy, as it has pattern subtraction, counting, and recursion all rolled into one. I've split that up into two lines in my solution: deltas and groups.

As an illustration of preferring "strategic" thinking over explicit recursion, consider the way deltas is computed:

xs = [100,103,106,112,118,121]
tail xs = [103,106,112,118,121]
zip (tail xs) xs = [(103,100), (106,103), (112,106), (118,112), (121,118)]
map ... = [3, 3, 6, 6, 3]

map (uncurry (-)) just means to perform subtraction for each tuple in the list. You could also write that as map (\(a, b) -> a - b).

Similarly, when defining groups, I avoid recursion by using map.