Zip With

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.