package functional

import functional.data.$\{$Graph$,$ Tree$\}$

trait Foldable$[$F$[\_]]$:

def fold Monoid $[A]$

def foldMap Monoid $[B]$ : $B$

object ListFoldable extends Foldable$[$List$]$:

override def fold : List $[A]($m: Monoid $[A]$ : $A=t$ match

case Nil $=>$ m$.$empty

case $,$ fold $(tl)(m)$

override def foldMap List $[A]$ Monoid $[B]???$

object TreeFoldable $//$ TODO

$|$

object GraphFoldable $//$ TODO

def wordCount$[$F$[\_]]($t: F$[$String$])($f: Foldable$[$F$])$: Int $=???$

def charCount$[$F$[\_]]($t: F$[$String$])($f: Foldable$[$F$])$: Int $=???$

$2$a$)$ Implement foldables $(5$ points$)$

The foldables for the data structures List, Tree and Graph need to be implemented.

Important: The given interfaces do not use any implicit parameters. You need to find the appropriate monoids explicitly

passed as a parameter.

Hints:

Two graphs can be merged using the monoid GraphMerge $($see task $1).$

The neighboring nodes of a graph can be edited using ListFoldable.

$2$b$)$ Apply foldables $(2$ points$)$

Task: Implement the two methods wordCount and charCount in functional.Foldable. The method

Example: wordCount$($List$("$hello world", "foo bar"$))($ListFoldable$)==4$

charCount should return the total number of characters in the strings contained within the foldable data structure.

Example: charCount$($List$("$hello world", "foo bar"$))($ListFoldable$)==18$