What does the functor do on the tree?

When people go into the woods

they can spot...

But if they look very carefully

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

But first things first

That's better!

Let's model this

Tree

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

Now what?

How's that useful?

Programming languages 🌳

The compiler parses your text file and produces an Abstract Syntax Tree (AST)

  • Allow you to analyze and manipulate the syntactic structure of programs
  • Useful in meta-programming

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".ignore) {
  2.     val oneLevelTree: Tree[String] =
  3.       Branch(
  4.         "/",
  5.         NonEmptyList
  6.           .of(
  7.             Leaf("bin"),
  8.             Leaf("boot"),
  9.             Leaf("etc"),
  10.             Branch("home", NonEmptyList.one(Leaf("majk"))),
  11.             Leaf("root"),
  12.             Leaf("usr"),
  13.             Leaf("var")
  14.           )
  15.       )
  17.     assertInlineSnapshot(
  18.       renderer.render(oneLevelTree),
  19.       """/
  20.         |β”œβ”€β”€ bin
  21.         |β”œβ”€β”€ boot
  22.         |β”œβ”€β”€ etc
  23.         |β”œβ”€β”€ home
  24.         |β”‚Β Β  └── majk
  25.         |β”œβ”€β”€ root
  26.         |β”œβ”€β”€ usr
  27.         |└── var""".stripMargin
  28.     )
  29.   }

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

Back to the source code

  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.     }

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

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

  2.   test("should visit nodes in expected order") {
  3.     val oneLevelTree: Tree[String] =
  4.       Branch(
  5.         "/",
  6.         NonEmptyList
  7.           .of(
  8.             Leaf("bin"),
  9.             Leaf("boot"),
  10.             Leaf("etc"),
  11.             Branch("home", NonEmptyList.one(Leaf("majk"))),
  12.             Leaf("root"),
  13.             Leaf("usr"),
  14.             Leaf("var")
  15.           )
  16.       )
  18.     assertInlineSnapshot(
  19.       BFS.breadthFirstList(oneLevelTree),
  20.       List("/", "bin", "boot", "etc", "home", "root", "usr", "var", "majk")
  21.     )
  22.   }

Let's see it in action

  1. sbt:root> testOnly *BFS*
  2. Visiting     /, queue: Queue()
  3. Visiting   bin, queue: Queue(boot, etc, home, root, usr, var)
  4. Visiting  boot, queue: Queue(etc, home, root, usr, var)
  5. Visiting   etc, queue: Queue(home, root, usr, var)
  6. Visiting  home, queue: Queue(root, usr, var)
  7. Visiting  root, queue: Queue(usr, var, majk)
  8. Visiting   usr, queue: Queue(var, majk)
  9. Visiting   var, queue: Queue(majk)
  10. Visiting  majk, queue: Queue()
  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

  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

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

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 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

  • RendererV3 should 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.     }

RendererV3 test

  1. val complexTree: Tree[String] =

RendererV3 test

  1.     val complexTree: Tree[String] =
  2.       Branch(
  3.         "/",
  4.         NonEmptyList.of(
  5.           Branch(
  6.             "home",
  7.             NonEmptyList.of(
  8.               Branch(
  9.                 "Documents",
  10.                 NonEmptyList.of(
  11.                   Leaf("report.pdf"),
  12.                   Leaf("thesis.docx")
  13.                 )
  14.               ),
  15.               Branch(
  16.                 "Projects",
  17.                 NonEmptyList.of(
  18.                   Leaf("project1/src/main.scala"),
  19.                   Leaf("project2/test/java/Main.java")
  20.                 )
  21.               )
  22.             )
  23.           ),
  24.           Branch(
  25.             "var",
  26.             NonEmptyList.of(
  27.               Leaf("log"),
  28.               Branch(
  29.                 "www",
  30.                 NonEmptyList.of(
  31.                   Leaf("html"),
  32.                   Leaf("css"),
  33.                   Leaf("js")
  34.                 )
  35.               )
  36.             )
  37.           ),
  38.           Branch(
  39.             "usr",
  40.             NonEmptyList.of(
  41.               Branch(
  42.                 "local",
  43.                 NonEmptyList.of(
  44.                   Branch(
  45.                     "share",
  46.                     NonEmptyList.of(
  47.                       Leaf("man"),
  48.                       Branch(
  49.                         "doc",
  50.                         NonEmptyList.of(
  51.                           Leaf("README.md"),
  52.                           Leaf("LICENSE")
  53.                         )
  54.                       )
  55.                     )
  56.                   )
  57.                 )
  58.               )
  59.             )
  60.           )
  61.         )
  62.       )

RendererV3 test

  1.   test("should render a complex tree") {
  2.     val complexTree: Tree[String] =
  3.       Branch(
  4.         "/",
  5.         NonEmptyList.of(
  6.       )
  7.     assertInlineSnapshot(
  8.       renderer.render(complexTree),
  9.       """ /
  10.         |β”œβ”€β”€ home
  11.         |β”‚  β”œβ”€β”€ Documents
  12.         |β”‚  β”‚  β”œβ”€β”€ report.pdf
  13.         |β”‚  β”‚  └── thesis.docx
  14.         |β”‚  └── Projects
  15.         |β”‚     β”œβ”€β”€ project1/src/main.scala
  16.         |β”‚     └── project2/test/java/Main.java
  17.         |β”œβ”€β”€ var
  18.         |β”‚  β”œβ”€β”€ log
  19.         |β”‚  └── www
  20.         |β”‚     β”œβ”€β”€ html
  21.         |β”‚     β”œβ”€β”€ css
  22.         |β”‚     └── js
  23.         |└── usr
  24.         |   └── local
  25.         |      └── share
  26.         |         β”œβ”€β”€ man
  27.         |         └── doc
  28.         |            β”œβ”€β”€ README.md
  29.         |            └── LICENSE""".stripMargin
  30.     )
  31.   }

Final challenge

Model the data

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. }

Model the data

  1.   object speakers {
  2.     val katarzyna = Speaker("Katarzyna Marek", "https://www.linkedin.com/in/katarzyna-marek-a74790193")
  3.     val rafal = Speaker("RafaΕ‚ Piotrowski", "https://www.linkedin.com/in/rafalpiotrowski")
  4.     val jakub = Speaker("Jakub Wojnowski", "https://www.linkedin.com/in/jakub-wojnowski")
  5.     val kacper = Speaker("Kacper Korban", "https://www.linkedin.com/in/kacperfkorban")
  6.     val michal = Speaker("MichaΕ‚ Pawlik", "https://michal.pawlik.dev")
  7.     val tomasz = Speaker("Tomasz Godzik", "https://twitter.com/TomekGodzik")
  8.   }
  10.   object talks {
  11.     // edition 10
  12.     val metals = Talk("All the things that Metals doesn't do")
  13.     val grackle = Talk("Grackle - Scala GraphQL Server")
  14.     // edition 11
  15.     val humanoIDs = Talk("Human(o)IDs β€” designing IDs for both machines AND humans")
  16.     val scala3Features = Talk("Scala 3 features you probably haven't used (yet)")
  17.     // edition 12
  18.     val functorOnTree = Talk("What does the functor do on the tree?")
  19.     val gearingTowarsOx = Talk("Gearing towards Ox: A look at structured concurrency and direct style Scala")
  20.   }
  22.   object events {
  23.     val event10 = Event(10, "15.05.2024")
  24.     val event11 = Event(11, "2.07.2024")
  25.     val event12 = Event(12, "17.09.2024")
  26.   }

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? πŸ•”

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

  • Kinds of traversal algorithms - DFS and BFS
  • Some of them are specialized like our labeling and rendering
  • Others are generic like map
  • Mixing imperative and FP is good and can be fun!

Thank you!

Keep in touch! 🀝

Blog: blog.michal.pawlik.dev
Linkedin: MichaΕ‚ Pawlik
Github: majk-p
Mastodon: majkp@hostux.social

Thank you!

Keep in touch! 🀝

Slides available at https://github.com/majk-p/functor-on-a-tree

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