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 []
To understand this, it is first important to understand how lists are represented in F#. An F# list is either:
[]
or 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
.