"Problem9": Packing a list

Question

I'm learning f# with no prior functional programming background - starting to make progress but been stuck on this one. Could anybody please help me understand the solution to Problem 9 of the 99 f# problems - they can be found here:[http://fssnip.net/an][1]

Basically I don't understand how the pattern matching works in the provided solution. For a start what is xss? cheers for any help!

Problem 9 : Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists.

Example:

pack ['a'; 'a'; 'a'; 'a'; 'b'; 'c'; 'c'; 'a'; 'a'; 'd'; 'e'; 'e'; 'e'; 'e']

val it : char list list = [['a'; 'a'; 'a'; 'a']; ['b']; ['c'; 'c']; ['a'; 'a']; ['d']; ['e'; 'e'; 'e'; 'e']]

Sample Solution;

let pack xs = 
    let collect x = function
        | (y::xs)::xss when x = y -> (x::y::xs)::xss
        | xss -> [x]::xss
    List.foldBack collect xs []

Answer 1

To understand this, it is first important to understand how lists are represented in F#. An F# list is either:

• an empty list written as [] or
• a value (head) followed by another list (tail) written as head::tail

So if you write, for example, [ 1; 2; 3 ] you are actually constructing a list containing 1, followed by a list containing 2, (etc.) followed by an empty list. The expression is compiled to:

1::(2::(3::[])) 

And you can omit the brackets and write just 1::2::3::[].

Pattern matching uses exactly the same syntax, but in the opposite direction. Instead of constructing lists, you are decomposing them. So when you have a pattern x::xs it means that you want to take the first element and assign it to a variable x and the remaining list should be assinged to a variable xs.

The pattern (x::xs)::xss is a bit more tricky, because it works on lists of lists. This means that the head of the list you match on is also a list. You could rewrite the code to the following simpler version:

let pack xs = 
    let collect x = function
        | head::xss ->    // Decompose into first element (head) and the rest (tail)
          match head with
          | y::xs when x = y -> (x::y::xs)::xss
          | _ -> [x]::xss
        | xss -> [x]::xss
    List.foldBack collect xs []

Now you have some duplication in the code, but you can see that collect takes x and another parameter, matches that another parameter against head::xss (to get the head/tail) and then also decomposes the head.

Answer 2

(y::xs)::xss matches a (non-empty) list of lists, y and xs being the head and tail of the first sublist and xss being the tail of the outer list. xss, in the second case, matches the entire list (empty or not).

foldBack (('T -> 'State -> 'State) -> 'T list -> 'State -> 'State) threads an accumulator argument through the list, going from back to front.

collect is the "accumulating" function, which basically reads: if the state (initially an empty list) contains at least one sublist, which is also non-empty, and the current element (x) matches the head of the sublist (y), prepend x to the sublist, otherwise prepend a new sublist to the state (xss) consisting solely of x. Each sublist is a group of equal, adjacent elements.