We were recently having a discussion in the Winnipeg .Net user group Katas channel, someone mentioned having a task to pretty print ranges. Given a list of sorted integers, consecutive values should be printed in a range. An example of [2, 3, 4, 5, 7, 9, 10, 11, 12, 15] would be printed as “2-5,7,9-12,15”.
Fold
I immediately reached for fold
. Initially using a list of lists for my accumulator, I then switched to a list of tuples. I was only ever storing two values, the upper and lower bounds of the range.
let printRange (input : int list) =
let pushSequential ts x =
match ts with
| (mn, mx) :: rs when mx + 1 = x -> (mn, x) :: rs
| _ -> (x, x) :: ts
let rangify = function
| mn, mx when mn = mx -> string mn
| mn, mx -> sprintf "%d-%d" mn mx
([], input)
||> Seq.fold pushSequential
|> Seq.map rangify
|> Seq.rev
|> (fun ranges -> System.String.Join(",", ranges))
The intermediate results after the Seq.fold
are: [(15,15);(9,12);(7,7);(2,5)]
. The remain functions convert the tuples to the appropriate range strings, reverse the list, and join the strings together.
Zip with
A Haskell solution presented used zipWith
. Although zipWith
is not built into the F# standard libraries, it’s not too difficult to create. zipWith
has a type signature of:
zipWith :: ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
In F#, we have zip
which takes two lists and generates a list of tuples.
zip :: 'a list -> 'b list -> ('a, 'b) list
zip
would be considered a specialized version of zipWith
due to the predefined output. Using zip
we can pair it with map
to create our own zipWith
.
let zipWith (mapper : 'a -> 'b -> 'c) (xs : 'a seq) (ys : 'b seq) =
Seq.zip xs ys |> Seq.map (fun (x,y) -> mapper x y)
We can now use our zipWith
to create another version of our solution.
let printRange (input : int list) =
let zipWith fn xs ys = ys |> Seq.zip xs |> Seq.map (fun (x,y) -> fn x y)
let display = function
| [x] -> string x
| x::xs -> xs |> Seq.last |> sprintf "%d-%d" x
input |> Seq.zip (zipWith (-) input { 1 .. System.Int32.MaxValue })
|> Seq.groupBy fst
|> Seq.map (snd >> Seq.map snd >> Seq.toList >> display)
|> (fun ranges -> System.String.Join(",", ranges))
The first few lines are setting up our zipWith
and a helper display
function to convert the list of ranges to a string. Let’s look at the line of zips.
input |> Seq.zip (input |> zipWith (-) { 1 .. System.Int32.MaxValue })
This line has a lot going on. The inner zipWith
function takes our input and a, relative, infinite sequence. We are subtracting the corresponding sequence values to obtain a grouping. We then zip
the grouping value with our original input. The intermediate result of that line, given the above input will look like:
[(1, 2); (1, 3); (1, 4); (1, 5); (2, 7); (3, 9); (3, 10); (3, 11); (3, 12); (5, 15)]
We then group by tuples by their assigned grouping values. The remaining code is there to unpack the tuples and transform the lists to string ranges to be concatenated and returned.
The twist
Both solutions achieve the desired results of "2-5,7,9-12,15"
for our sample input. The best part of this was we were asked about a PowerShell solution. We totally didn’t help but it sure was fun. I figured I would give a PowerShell version a try.
function rangify([int[]] $numbers) {
$sequenced = [Linq.Enumerable]::Zip(
[Linq.Enumerable]::Zip($numbers,
[Linq.Enumerable]::Range(1,[int]::MaxValue),
[Func[int,int,int]] { $args[0] - $args[1]} ),
$numbers,
[Func[int, int, System.Collections.Specialized.OrderedDictionary]] `
{ [ordered]@{ Value = $args[1]; Group = $args[0]} })
$grouped = [Linq.Enumerable]::GroupBy($sequenced,
[Func[System.Collections.Specialized.OrderedDictionary,int]] `
{ $args[0]['Group'] })
$mapped = [Linq.Enumerable]::Select($grouped,
[Func[System.Linq.IGrouping[int, System.Collections.Specialized.OrderedDictionary], string]] `
{
$list = $args[0].Value
if ($list.Length -gt 1) {
$min = $list[0]
$max = $list[$list.Length-1]
return "$min-$max"
} else {
return $list[0]
}
})
return [System.String]::Join(",", $mapped)
}
The PowerShell solution uses C# Linq’s zip
which is really a version of zipWith
. It works and it’s mainly type signatures.