$1)$

package functional

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

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

def fold$[$A$]($t: F$[$A$])($m: Monoid$[$A$])$: A

def foldMap$[$A$,$ B$]($t: F$[$A$])($f: A $=>$ B$)($m: Monoid$[$B$])$: B

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

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

case Nil $=>$ m$.$empty

case hd :: tl $=>$ m$.$combine$($hd$,$ fold$($tl$)($m$))$

override def foldMap$[$A$,$ B$]($t: List$[$A$])($f: A $=>$ B$)($m: Monoid$[$B$])$: 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)$

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

$1.$ Task: Complete the implementations of the foldables in functional.Foldable. Extend the given objects so that they inherit from Foldable and implement the necessary methods.

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

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

$4.$ passed as a parameter.

$5.$ Hints:

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

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

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

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

$10.$ wordCount is intended to accumulate the number of words in the strings contained within the foldable data structure. Assume all words are separated by a space.

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

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

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

$14.$