Search code examples
listf#pattern-matchingmatchingpacking

"Problem9": Packing a list


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 []

Solution

  • 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.