use context essentials2021

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

import lists as L
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"
  ... gossip.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
|#


GINNY-GOSSIP =
  gossip("Ginny", 
    [list: ])

ROMILDA-GOSSIP =
  gossip("Romilda", 
    [list: GINNY-GOSSIP])

VINCENT-GOSSIP =
  gossip("Vincent", 
    [list: ])

DRACO-GOSSIP =
  gossip("Draco", 
    [list: VINCENT-GOSSIP])

CHO-GOSSIP =
  gossip("Cho", 
    [list: ])

PANSY-GOSSIP =
  gossip("Pansy", 
    [list: DRACO-GOSSIP, CHO-GOSSIP, ROMILDA-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(GINNY-GOSSIP) is 1
  count-gossips(PANSY-GOSSIP) is 6
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([list: DRACO-GOSSIP, CHO-GOSSIP, ROMILDA-GOSSIP]) is 5
end


#|
# Shorter version using higher-order functions
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)"
  M.sum(L.map(count-gossips, log))
where:
  count-gossips-in-list([list: ]) is 0
  count-gossips-in-list([list: DRACO-GOSSIP, CHO-GOSSIP, ROMILDA-GOSSIP]) is 5
end
|#