use context essentials2021

# CMPU 101, Section 52
# 20 February 2023

# A more realistic rumor mill, where each gossip can tell any number of other people -- i.e., an arbitrary tree


import math as M

data Gossip:
  | gossip(name :: String, next :: List<Gossip>)
end


#|
fun gossip-template(g :: Gossip) -> ...:
  doc: "Template for a function that takes a gossip"
  ... g.name
  ... log-template(g.next)
where:
  gossip-template(...) is ...
end

fun log-template(l :: List<Gossip>) -> ...:
  doc: "Template for a function that takes a list of gossip"
  cases (List) l:
    | empty => ...
    | link(f, r) =>
      ... gossip-template(f)
      ... log-template(r)
  end
where:
  log-template(...) is ...
end
|#


MRS-COLE-GOSSIP =
  gossip("Mrs Cole",
    [list: ])

MRS-PERRY-GOSSIP =
  gossip("Mrs Perry",
    [list: ])

MRS-ELTON-GOSSIP =
  gossip("Mrs Elton",
    [list: ])

JANE-GOSSIP =
  gossip("Jane",
    [list: ])

MISS-BATES-GOSSIP =
  gossip("Miss Bates",
    [list: MRS-COLE-GOSSIP, MRS-PERRY-GOSSIP, MRS-ELTON-GOSSIP])

MR-WOODHOUSE-GOSSIP =
  gossip("Mr Woodhouse", 
    [list: ])

MRS-WESTON-GOSSIP =
  gossip("Mrs Weston", 
    [list: ])

MR-WESTON-GOSSIP =
  gossip("Mr Weston",
    [list: JANE-GOSSIP, MISS-BATES-GOSSIP])

EMMA-GOSSIP = 
  gossip("Emma",
    [list: MR-WOODHOUSE-GOSSIP, MRS-WESTON-GOSSIP, 
      MR-WESTON-GOSSIP])


fun count-gossips(g :: Gossip) -> Number:
  doc: "Count all the people who hear a rumor that the given gossip (person) knows"
  1 + count-gossips-in-list(g.next)
where:
  count-gossips(MRS-COLE-GOSSIP) is 1
  count-gossips(EMMA-GOSSIP) is 9
end


# Straightforward recursive version
fun count-gossips-in-list(log :: List<Gossip>) -> Number:
  doc: "Count all the people informed by the people in the list (assuming they're all different)"

  cases (List) log:
    | empty => 0
    | link(f, r) =>
      count-gossips(f) + count-gossips-in-list(r)
  end

where:
  count-gossips-in-list([list: ]) is 0
  count-gossips-in-list(EMMA-GOSSIP.next) is 8
end


# We could also write `count-gossips-in-list` without explicit recursion:

#|
fun count-gossips-in-list(l :: List<Gossip>) -> Number:
  doc: "Count how many people are informed in a list of gossips"

  M.sum(map(count-gossips, l))

where:
  count-gossips-in-list([list: ]) is 0
  count-gossips-in-list(EMMA-GOSSIP.next) is 8
end
|#


# And then we see that we could fold that function into `count-gossips` itself, solving the problem with just one function definition:

#|
fun count-gossips(g :: Gossip) -> Number:
  doc: "Count how many people are informed by a gossip (including the gossip themself)"
  1 + M.sum(map(count-gossips, g.next))
where:
  count-gossips(MRS-COLE-GOSSIP) is 1
  count-gossips(EMMA-GOSSIP) is 9
end
|#