CODEWITHSUNDEEP
f#tree
Khaine775
Khaine775

Reputation: 2765

F# Traversing mutually recursive tree to count elements

Given the following types:

type Title    = string
type Document = Title * Element list
and Element   = Par of string | Sec of Document

I'm attempting to create a function which will traverse the tree and count the number of occurrences of Sec.

Given the following example:

let s1  = ("section 1", [Par "Bla"])
let s2  = ("section 2", [Sec s21; Par "Bla"])
let s21 = ("subsection 2.1", [Par "Bla"])
let s3  = ("section 3", [Par "Bla"])
let doc = ("Compiler project", [Par "Bla"; Sec s1; Sec s2; Sec s3]);

A function taking a Document to count number of Sections, noOfSecs d would in this case return 4, as there are 4 Sections in this case. I've attempted something, but I'm a little stuck, especially what to do when I hit a Par:

let rec noOfSecs d =
    match d with
    | (_,[])    -> 0
    | (_,e::es) -> (findSecs e)
and findSecs = function
    | Sec(t,_::es) -> 1 + noOfSecs (t,es)
    | Par p        -> //What should we do here?

Upvotes: 3

Views: 237

Answers (1)

Lee
Lee

Reputation: 144126

There are 0 Secs within a Par string so you can return 0 for that case. In noOfSecs you need to sum the Sec cases for each element in the element list, not just the first one. You can use List.sumBy for this:

let rec noOfSecs (_, elems) =
    List.sumBy findSecs elems
and findSecs = function
    | Sec d -> 1 + noOfSecs d
    | Par p        -> 0

Upvotes: 4

Related Questions