What does the functor do on the tree?

When you go into the woods

you can spot...

But if you look very carefully

Hi πŸ‘‹ My name is MichaΕ‚ Pawlik

  • Senior Software engineer @ SiriusXM
  • Blog about Scala
  • Occasional OSS

Tree

That's better!

Tree

  1. enum Tree[A] {
  2.   case Branch(value: A, branches: NonEmptyList[Tree[A]])
  3.   case Leaf(value: A)

How's that useful?

AST

Databases 🌳

Self-balancing tree called B-tree is a popular way to implement indexing in databases

File system 🌳

  • / is the Root
  • Directories are branches
  • Files are leaves

Files tree

  1. .
  2. β”œβ”€β”€ build.sbt
  3. β”œβ”€β”€ docs
  4. β”‚Β Β  └── markdown
  5. β”‚Β Β      β”œβ”€β”€ contributing
  6. β”‚Β Β      β”‚Β Β  β”œβ”€β”€ how-it-works.md
  7. β”‚Β Β      β”‚Β Β  β”œβ”€β”€ index.md
  8. β”‚Β Β      β”‚Β Β  └── supporting-a-test-framework.md
  9. β”‚Β Β      β”œβ”€β”€ custom-types-support.md
  10. β”‚Β Β      └── supported-frameworks.md
  11. β”œβ”€β”€ LICENSE
  12. β”œβ”€β”€ modules
  13. β”‚Β Β  β”œβ”€β”€ core
  14. β”‚Β Β  β”œβ”€β”€ hashing
  15. β”‚Β Β  β”œβ”€β”€ munit
  16. β”‚Β Β  β”œβ”€β”€ plugin
  17. β”‚Β Β  β”œβ”€β”€ scalatest
  18. β”‚Β Β  └── weaver
  19. β”œβ”€β”€ project
  20. β”‚Β Β  β”œβ”€β”€ build.properties
  21. β”‚Β Β  β”œβ”€β”€ plugins.sbt
  22. β”‚Β Β  β”œβ”€β”€ project
  23. β”‚Β Β  └── Versions.scala
  24. β”œβ”€β”€ README.md
  25. └── website
  26.     β”œβ”€β”€ babel.config.js
  27.     β”œβ”€β”€ docs
  28.     β”œβ”€β”€ docusaurus.config.ts
  29.     └── static
  30.         └── img
  31.             β”œβ”€β”€ favicon.ico
  32.             β”œβ”€β”€ logo-large.png
  33.             β”œβ”€β”€ logo-medium.png
  34.             └── logo-small.png

Wait that looked quite nice πŸ€”

Wait that looked quite nice πŸ€”

How about we implement a renderer like this for our tree?

Goal πŸ₯…

Draw a tree of meetup editions with topics as sub-trees 🌳 and speaker info as leafs πŸ€

Goal πŸ₯…

  1.  WrocΕ‚aw Scala User Group
  2. β”œβ”€β”€ πŸ“… 15.05.2024 Meeting #10
  3. β”‚  β”œβ”€β”€ 🎀 All the things that Metals doesn't do
  4. β”‚  β”‚  └── 🧍 Katarzyna Marek 🌐 https://www.linkedin.com/in/katarzyna-marek-a74790193
  5. β”‚  └── 🎀 Grackle - Scala GraphQL Server
  6. β”‚     └── 🧍RafaΕ‚ Piotrowski 🌐 https://www.linkedin.com/in/rafalpiotrowski
  7. β”œβ”€β”€ πŸ“… 2.07.2024 Meeting #11
  8. β”‚  β”œβ”€β”€ 🎀 Human(o)IDs β€” designing IDs for both machines AND humans
  9. β”‚  β”‚  └── 🧍 Jakub Wojnowski 🌐 https://www.linkedin.com/in/jakub-wojnowski
  10. β”‚  └── 🎀 Scala 3 features you probably haven't used (yet)
  11. β”‚     └── 🧍   Kacper Korban 🌐 https://www.linkedin.com/in/kacperfkorban
  12. └── πŸ“… 17.09.2024 Meeting #12
  13.    β”œβ”€β”€ 🎀 What does the functor do on the tree?
  14.    β”‚  └── 🧍   MichaΕ‚ Pawlik 🌐 https://michal.pawlik.dev
  15.    └── 🎀 Gearing towards Ox: A look at structured concurrency and direct style Scala
  16.       └── 🧍   Tomasz Godzik 🌐 https://twitter.com/TomekGodzik

But how πŸ€”

  • Renderer capable of drawing simple structure
  • Renderer capable of drawing nested structure
  • Model meetup details
  • Render tree with meetup details

Renderer

  1. trait Renderer {
  2.   def render(tree: Tree[String]): String
  3. }

Baby steps πŸ‘Ά

Let's start with drawing this:

  1. /
  2. β”œβ”€β”€ bin
  3. β”œβ”€β”€ boot
  4. β”œβ”€β”€ etc
  5. β”œβ”€β”€ home
  6. β”œβ”€β”€ root
  7. β”œβ”€β”€ usr
  8. └── var

Test

  1.   test("should render a simple tree".ignore) {
  2.     val oneLevelTree: Tree[String] =
  3.       Branch(
  4.         "/",
  5.         NonEmptyList
  6.           .of("bin", "boot", "etc", "home", "root", "usr", "var")
  7.           .map(Leaf(_))
  8.       )
  10.     assertInlineSnapshot(
  11.       renderer.render(oneLevelTree),
  12.       """/
  13.         |β”œβ”€β”€ bin
  14.         |β”œβ”€β”€ boot
  15.         |β”œβ”€β”€ etc
  16.         |β”œβ”€β”€ home
  17.         |β”œβ”€β”€ root
  18.         |β”œβ”€β”€ usr
  19.         |└── var""".stripMargin
  20.     )
  21.   }
  22.

Snapshot4s πŸ“Έ

https://github.com/siriusxm/snapshot4s

Renderer

  1.   def render(tree: Tree[String]): String =
  2.     tree match {
  3.       case Tree.Branch(value, branches) =>
  4.         val renderedBranches =
  5.           branches
  6.             .map(render(_))
  7.             .toList
  8.             .mkString("\n")
  9.         show"$value\n$renderedBranches"
  11.       case Tree.Leaf(value) => show"β”œβ”€β”€ $value"
  12.     }

Let's test it!

Snapshot test result

  1. Snapshot not equal
  2. => Obtained
  3. /
  4. β”œβ”€β”€ bin
  5. β”œβ”€β”€ boot
  6. β”œβ”€β”€ etc
  7. β”œβ”€β”€ home
  8. β”œβ”€β”€ root
  9. β”œβ”€β”€ usr
  10. β”œβ”€β”€ var
  11. => Diff (- obtained, + expected)
  12.  β”œβ”€β”€ usr
  13. -β”œβ”€β”€ var
  14. +└── var

The missing └──

Renderer

  1.   def render(tree: Tree[String]): String =
  2.     tree match {
  3.       case Tree.Branch(value, branches) =>
  4.         val renderedBranches =
  5.           branches
  6.             .map(render(_))
  7.             .toList
  8.             .mkString("\n")
  9.         show"$value\n$renderedBranches"
  11.       case Tree.Leaf(value) => show"β”œβ”€β”€ $value"
  12.     }

RendererV2

  1.   def render(tree: Tree[String]): String =
  2.     renderRecursive(tree, true)
  4.   private def renderRecursive[A: Show](tree: Tree[A], isLast: Boolean): String =
  5.     tree match {
  6.       case Tree.Branch(value, branches) =>
  7.         val allButLast = branches.init.map(
  8.           renderRecursive(_, isLast = false)
  9.         )
  10.         val lastBranch = renderRecursive(
  11.           branches.last,
  12.           isLast = true
  13.         )
  14.         val renderedBranches = (allButLast :+ lastBranch).mkString("\n")
  15.         show"$value\n$renderedBranches"
  17.       case Tree.Leaf(value) =>
  18.         if (isLast) show"└── $value"
  19.         else show"β”œβ”€β”€ $value"
  20.     }

Test again

  1.   test("should render a simple tree") {
  2.     val oneLevelTree: Tree[String] =
  3.       Branch(
  4.         "/",
  5.         NonEmptyList
  6.           .of("bin", "boot", "etc", "home", "root", "usr", "var")
  7.           .map(Leaf(_))
  8.       )
  10.     assertInlineSnapshot(
  11.       renderer.render(oneLevelTree),
  12.       """/
  13.         |β”œβ”€β”€ bin
  14.         |β”œβ”€β”€ boot
  15.         |β”œβ”€β”€ etc
  16.         |β”œβ”€β”€ home
  17.         |β”œβ”€β”€ root
  18.         |β”œβ”€β”€ usr
  19.         |└── var""".stripMargin
  20.     )
  21.   }

So far so good!

  1. RendererV2Test:
  2.   + should render a simple tree 0.266s

Nesting πŸͺœ

Can we handle nested structures?

Nesting πŸͺœ

Can we handle nested structures?

  1. /
  2. β”œβ”€β”€ bin
  3. β”œβ”€β”€ boot
  4. β”œβ”€β”€ etc
  5. β”œβ”€β”€ home
  6. β”‚Β Β  └── majk
  7. β”œβ”€β”€ root
  8. β”œβ”€β”€ usr
  9. └── var

Let's test it

  1. test("should render one level tree") {
  2.   val oneLevelTree: Tree[String] =
  3.     Branch(
  4.       "/",
  5.       NonEmptyList
  6.         .of(
  7.           Leaf("bin"), /*...*/,
  8.           Branch("home", NonEmptyList.one(Leaf("majk"))),
  9.           /*...*/Leaf("var")
  10.         )
  11.     )
  12.   assertInlineSnapshot(
  13.     renderer.render(oneLevelTree),
  14.     """/
  15.       |β”œβ”€β”€ bin
  16.       |β”œβ”€β”€ boot
  17.       |β”œβ”€β”€ etc
  18.       |β”œβ”€β”€ home
  19.       |β”‚   └── majk
  20.       |β”œβ”€β”€ root
  21.       |β”œβ”€β”€ usr
  22.       |└── var""".stripMargin
  23.   )
  24. }

Not quite!

  1. Snapshot not equal
  2. => Obtained
  3. /
  4. β”œβ”€β”€ bin
  5. β”œβ”€β”€ boot
  6. β”œβ”€β”€ etc
  7. home
  8. └── majk
  9. β”œβ”€β”€ root
  10. β”œβ”€β”€ usr
  11. └── var
  12. => Diff (- obtained, + expected)
  13.  β”œβ”€β”€ etc
  14. -home
  15. -└── majk
  16. +β”œβ”€β”€ home
  17. +β”‚Β Β  └── majk
  18.  β”œβ”€β”€ root

Why doesn't it work? πŸ€”

Depth-first search

Depth-first search

  1.   def render(tree: Tree[String]): String =
  2.     tree match {
  3.       case Tree.Branch(value, branches) =>
  4.         val renderedBranches =
  5.           branches
  6.             .map(render(_))
  7.             .toList
  8.             .mkString("\n")
  9.         show"$value\n$renderedBranches"
  11.       case Tree.Leaf(value) => show"β”œβ”€β”€ $value"
  12.     }

Is this strategy good enough anyway?

Step by step

Let's do depth first search on a simplified tree

  1. /
  2. β”œβ”€β”€ bin
  3. β”œβ”€β”€ boot
  4. β”œβ”€β”€ home
  5. β”‚Β Β  └── majk
  6. └── root

Step by step

  1. /
  2. β”œβ”€β”€ bin
  3. ...

Step by step

  1. /
  2. β”œβ”€β”€ bin
  3. β”œβ”€β”€ boot
  4. ...

Step by step

  1. /
  2. β”œβ”€β”€ bin
  3. β”œβ”€β”€ boot
  4. β”œβ”€β”€ home
  5. ...

Step by step

  1. /
  2. β”œβ”€β”€ bin
  3. β”œβ”€β”€ boot
  4. ❓─ home
  5. ❓  └── majk

πŸ€” what should the first character be?

Limitations of DFS

  • We want to draw trees in depth-first manner, but we lack information about the structure
  • We need to learn the tree width first, before deciding how to print nodes

Breadth-first search

Black: explored

Grey: queued to be explored later on

  • You got this right, we're introducing a mutable queue!

Basic BFS

  2.   def breadthFirstList[A](root: Tree[A]): List[A] = {
  3.     val q = Queue.empty[Tree[A]]
  4.     val results = ListBuffer.empty[A]
  5.     q.enqueue(root)
  6.     while (q.nonEmpty) {

πŸ™ˆ

  1.     }
  2.     results.toList

Basic BFS

  1.   def breadthFirstList[A](root: Tree[A]): List[A] = {
  2.     val q = Queue.empty[Tree[A]]
  3.     val results = ListBuffer.empty[A]
  4.     q.enqueue(root)
  5.     while (q.nonEmpty) {
  6.       val node = q.dequeue()
  7.       println(f"Visiting ${node.getValue}%5s, queue: ${q.map(_.getValue)}")
  8.       node match
  9.         case Tree.Branch(value, branches) =>
  10.           results.append(value)
  11.           q.enqueueAll(branches.toList)
  12.         case Tree.Leaf(value) =>
  13.           results.append(value)
  14.     }
  15.     results.toList
  16.   }

Let's test it

For our test tree

  1. /
  2. β”œβ”€β”€ bin
  3. β”œβ”€β”€ boot
  4. β”œβ”€β”€ etc
  5. β”œβ”€β”€ home
  6. β”‚Β Β  └── majk
  7. β”œβ”€β”€ root
  8. β”œβ”€β”€ usr
  9. └── var

Let's see it in action

  1. sbt:root> testOnly *BFS*
  2. queue: Queue()                                 Visiting     /
  3. queue: Queue(boot, etc, home, root, usr, var)  Visiting   bin
  4. queue: Queue(etc, home, root, usr, var)        Visiting  boot
  5. queue: Queue(home, root, usr, var)             Visiting   etc
  6. queue: Queue(root, usr, var)                   Visiting  home
  7. queue: Queue(usr, var, majk)                   Visiting  root
  8. queue: Queue(var, majk)                        Visiting   usr
  9. queue: Queue(majk)                             Visiting   var
  10. queue: Queue()                                 Visiting  majk
  11. BFSTest:
  12.   + should visit nodes in expected order 0.124s
  13. [info] Passed: Total 1, Failed 0, Errors 0, Passed 1

So far so good, ordering makes sense

Now let's attach some info along the way

Node positioning

Here's what we expect

  1. /
  2. β”œβ”€β”€ bin         | First
  3. β”œβ”€β”€ boot        | Middle
  4. β”œβ”€β”€ etc         | Middle
  5. β”œβ”€β”€ home        | Middle
  6. β”‚Β Β  └── majk    | Middle -> Last
  7. β”œβ”€β”€ root        | Middle
  8. β”œβ”€β”€ usr         | Middle
  9. └── var         | Last

Node positioning

  1.   enum Alignment {
  2.     case First
  3.     case Middle
  4.     case Last
  5.   }

Node positioning

  1.   enum Alignment {
  2.     case First
  3.     case Middle
  4.     case Last
  5.   }

  1.   def labelNodes[A](root: Tree[A]): List[(A, List[Alignment])] = {

Extended queue and result type

  1.   def labelNodes[A](root: Tree[A]): List[(A, List[Alignment])] = {
  2.     val q = Queue.empty[(Tree[A], List[Alignment])]
  3.     val results = ListBuffer.empty[(A, List[Alignment])]
  4.     q.enqueue((root, List.empty))
  5.     while (q.nonEmpty) {

  1.     }
  2.     results.toList

Extended queue and result type

  1.     while (q.nonEmpty) {
  2.       val (node, alignments) = q.dequeue()
  3.       node match
  4.         case Tree.Branch(value, branches) =>
  5.           val branchesWithPositions =
  6.             attachPositions(alignments)(branches.toList)
  7.           results.append((value, alignments))
  8.           q.enqueueAll(branchesWithPositions)
  9.         case Tree.Leaf(value) =>
  10.           results.append((value, alignments))

Extended queue and result type

  1.   private def attachPositions[A](parantPositions: List[Alignment])(
  2.       branches: List[Tree[A]]
  3.   ): List[(Tree[A], List[Alignment])] =
  4.     branches.zipWithIndex.map { case (tree, index) =>
  5.       (tree, parantPositions.appended(calculatePosition(index, branches.size)))
  6.     }

  2.   private def calculatePosition(idx: Int, size: Int): Alignment =
  3.     if (idx == size - 1) Alignment.Last
  4.     else if (idx == 0) Alignment.First
  5.     else Alignment.Middle

Let's test it

For our test tree

  1. /
  2. β”œβ”€β”€ bin         | First
  3. β”œβ”€β”€ boot        | Middle
  4. β”œβ”€β”€ etc         | Middle
  5. β”œβ”€β”€ home        | Middle
  6. β”‚Β Β  └── majk    | Middle -> Last
  7. β”œβ”€β”€ root        | Middle
  8. β”œβ”€β”€ usr         | Middle
  9. └── var         | Last

Let's test it

  2.   test("should produce extended alignments") {
  3.     assertInlineSnapshot(
  4.       BFSExtended.labelNodes(oneLevelTree),
  5.       List(
  6.         ("/", List()),
  7.         ("bin", List(First)),
  8.         ("boot", List(Middle)),
  9.         ("etc", List(Middle)),
  10.         ("home", List(Middle)),
  11.         ("root", List(Middle)),
  12.         ("usr", List(Middle)),
  13.         ("var", List(Last)),
  14.         ("majk", List(Middle, Last))
  15.       )
  16.     )
  17.   }

Works like a charm

  1. BFSTest:
  2.   + should visit nodes in expected order 0.078s
  3.   + should produce paddings 0.018s
  4.   + should produce extended alignments 0.007s

We are ready

We are ready

  • First do BFS to learn the structure,
  • Then DFS to draw in correct order

RendererV3 implementation

  1. object RendererV3 extends Renderer {
  3.   def render(tree: Tree[String]): String = {
  4.     val mapping = BFSExtended.labelNodes(tree).toMap
  5.     renderRecursive(tree, mapping)
  6.   }

RendererV3 implementation

  1.   private def renderRecursive[A: Show](
  2.       tree: Tree[A],
  3.       mapping: Map[A, List[Alignment]]
  4.   ): String = {
  5.     val alignments = mapping.get(tree.getValue).getOrElse(List.empty)
  6.     val renderedPrefix = renderAlignments(alignments)
  7.     tree match {
  8.       case Tree.Branch(value, branches) =>
  9.         val renderedBranches =
  10.           branches.map(renderRecursive(_, mapping)).toList.mkString("\n")
  11.         show"$renderedPrefix $value\n$renderedBranches"
  13.       case Tree.Leaf(value) =>
  14.         show"$renderedPrefix $value"
  15.     }
  16.   }

RendererV3 implementation

  1.   private def renderAlignments(alignments: List[Alignment]) =
  2.     alignments.zipWithIndex
  3.       .map((alignment, idx) => (alignment, idx == alignments.size - 1))
  4.       .map(renderAlignment)
  5.       .mkString
  7.   private def renderAlignment(alignment: Alignment, lastBranch: Boolean) =
  8.     alignment match {
  9.       case Alignment.First | Alignment.Middle if (lastBranch)  => "β”œβ”€β”€"
  10.       case Alignment.First | Alignment.Middle if (!lastBranch) => "β”‚  "
  11.       case Alignment.Last if (lastBranch)                      => "└──"
  12.       case Alignment.Last if (!lastBranch)                     => "   "
  13.     }

Final challenge

Model the data

  1. case class Event(edition: Int, date: String) {
  2.   val render = s"πŸ“… ${date} Meeting #${edition}"
  3. }
  4. case class Talk(title: String) {
  5.   val render = s"🎀 ${title}"
  6. }
  7. case class Speaker(name: String, social: String) {
  8.   val render = f"🧍${name}%16s 🌐 ${social}"
  9. }

Tree of String

  • We know how to print Tree[String]
  • We need to turn Tree[Event | Talk | Speaker | String] into Tree[String]

Do you know what time it is? πŸ•”

No, not the lunch break yet 🌯 🍲

It's time for...

The F word

Functor

Functor

Provided we have Event | Talk | Speaker| String => String

Functor can turn Tree[Event | Talk | Speaker | String] into Tree[String]

Functor[F[_]] on a Tree[A] 🌳

Functor on a Tree[A] 🌳

  1. object Tree {
  2.   given Functor[Tree] = new Functor[Tree] {
  3.     def map[A, B](fa: Tree[A])(f: A => B): Tree[B] =
  4.       fa match
  5.         case Branch(value, branches) =>
  6.           Branch(
  7.             f(value),
  8.             branches.map(map(_)(f))
  9.           )
  10.         case Leaf(value) => Leaf(f(value))
  11.   }
  13. }

Functor[F[_]] on a Tree[A] 🌳

Functor can turn Tree[Event | Talk | Speaker | String] into Tree[String]

  1.   def renderMeetup(meetupNode: Event | Talk | Speaker | String) =
  2.     meetupNode match {
  3.       case v: Event   => v.render
  4.       case v: Talk    => v.render
  5.       case v: Speaker => v.render
  6.       case v: String  => v
  7.     }

  1.     val meetup: Tree[Event | Talk | Speaker | String] =
  2.     val converted: Tree[String] = meetup.map(renderMeetup)

Functor[F[_]] on a Tree[A] 🌳

  1.     val meetup: Tree[Event | Talk | Speaker | String] =
  2.       Branch(
  3.         "WrocΕ‚aw Scala User Group",
  4.         NonEmptyList
  5.           .of(
  6.             Branch(
  7.               events.event10,
  8.               NonEmptyList.of(
  9.                 Branch(talks.metals, NonEmptyList.of(Leaf(speakers.katarzyna))),
  10.                 Branch(talks.grackle, NonEmptyList.of(Leaf(speakers.rafal)))
  11.               )
  12.             ),
  13.             Branch(
  14.               events.event11,
  15.               NonEmptyList.of(
  16.                 Branch(talks.humanoIDs, NonEmptyList.of(Leaf(speakers.jakub))),
  17.                 Branch(talks.scala3Features, NonEmptyList.of(Leaf(speakers.kacper)))
  18.               )
  19.             ),
  20.             Branch(
  21.               events.event12,
  22.               NonEmptyList.of(
  23.                 Branch(talks.functorOnTree, NonEmptyList.of(Leaf(speakers.michal))),
  24.                 Branch(talks.gearingTowarsOx, NonEmptyList.of(Leaf(speakers.tomasz)))
  25.               )
  26.             )
  27.           )
  28.       )

Final result

Final result

  1.  WrocΕ‚aw Scala User Group
  2. β”œβ”€β”€ πŸ“… 15.05.2024 Meeting #10
  3. β”‚  β”œβ”€β”€ 🎀 All the things that Metals doesn't do
  4. β”‚  β”‚  └── 🧍 Katarzyna Marek 🌐 https://www.linkedin.com/in/katarzyna-marek-a74790193
  5. β”‚  └── 🎀 Grackle - Scala GraphQL Server
  6. β”‚     └── 🧍RafaΕ‚ Piotrowski 🌐 https://www.linkedin.com/in/rafalpiotrowski
  7. β”œβ”€β”€ πŸ“… 2.07.2024 Meeting #11
  8. β”‚  β”œβ”€β”€ 🎀 Human(o)IDs β€” designing IDs for both machines AND humans
  9. β”‚  β”‚  └── 🧍 Jakub Wojnowski 🌐 https://www.linkedin.com/in/jakub-wojnowski
  10. β”‚  └── 🎀 Scala 3 features you probably haven't used (yet)
  11. β”‚     └── 🧍   Kacper Korban 🌐 https://www.linkedin.com/in/kacperfkorban
  12. └── πŸ“… 17.09.2024 Meeting #12
  13.    β”œβ”€β”€ 🎀 What does the functor do on the tree?
  14.    β”‚  └── 🧍   MichaΕ‚ Pawlik 🌐 https://michal.pawlik.dev
  15.    └── 🎀 Gearing towards Ox: A look at structured concurrency and direct style Scala
  16.       └── 🧍   Tomasz Godzik 🌐 https://twitter.com/TomekGodzik

Takeaways

It's not FP vs OOP

It's FP and OOP!

  • With Scala you get the best of both worlds 🌍
  • Choose the right tools for the problem 🧰

Thank you!

Blog: blog.michal.pawlik.dev
Linkedin: MichaΕ‚ Pawlik
Github: majk-p
Bluesky: @michal.pawlik.dev

Get in touch! πŸ‘‹

Bonus

![bg blur:5px brightness:0.5](./img/path-dog1.jpg) # Path for today 1) Model a `Tree` with `ADT` * what is a tree * normal people see birds or cats on trees * our trees are upside down * and if we have a really close look, we can see a functor on them 2) Identify the `Functor` on the `Tree` 3) Everyday `Tree` in IT * Source code * Filesystem and the `tree` command 4) Drawing our own tree * Goal: draw a timeline of WSUG * First just edition names + times * Then subtrees with topics and authors * Then sub-subtrees with author details like website or socials * Depth first - functional approach * Breadth-first - imperative * Compile it together * Homework: Okasaki structure for FP breadth-first

![bg blur:5px brightness:0.4](./img/path-dog1.jpg) # Path for today 1) Model a `Tree` with `ADT` 2) Identify the `Functor` on the `Tree` 3) Everyday `Tree` in IT 4) Draw yourself a `Tree`

TODO make a slide with showcasing the expected result

draw the tree from the example above and show how when visiting `majk` leaf we don't know if there are other nodes on the upper level

draw the tree from the example above and show how when visiting `majk` leaf we don't know if there are other nodes on the upper level

NOTE: we are not handling duplicates here, that's a bonus question