Last active
August 29, 2015 14:18
-
-
Save cedricbastin/a2aa1c81c92194b77cdf to your computer and use it in GitHub Desktop.
exploring lazy evaluation to avoid multiple passes over a tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| object Main extends App { | |
| /* | |
| * Exploring lazy evaluation in Scala to replace all nodes in a tree with the minimum value of the tree in 1 pass | |
| * thanks to @begeric | |
| */ | |
| sealed trait Tree | |
| case class Node(tl:Tree, v:Int, t2:Tree) extends Tree | |
| case object Leaf extends Tree | |
| /* | |
| * we give a concrete tree as input and a lazy value min which will eventually contain the minimum of all nodes | |
| * we will lazily construct a new Node which will use the minimum once available | |
| */ | |
| def minTree(tree:Tree):Tree = { | |
| /* | |
| * the min input is lazy as it will only be available after a first pass through the tree | |
| * the result is a tuple such that we can return both the not yet constructed tree and the calculated minimum | |
| */ | |
| def rec(t: Tree, min: => Int):(() => Tree, Int) = { | |
| t match { | |
| case Node(tl, v, tr) => | |
| val l = rec(tl, min) | |
| val r = rec(tr, min) | |
| //the minima from both subnodes are available and are thus concrete | |
| val cmin = Math.min(v, Math.min(l._2, r._2)) | |
| (() => Node(l._1(), min, r._1()), cmin) | |
| case Leaf => (() => Leaf, Int.MaxValue) //initial empty acc | |
| } | |
| } | |
| // as min is a recursive value it need a type | |
| lazy val (res, min:Int) = rec(tree, min) | |
| // evaluate the lazy tree as min is now available | |
| res() | |
| } | |
| println(minTree(Node(Node(Node(Leaf, 2, Leaf), 1, Leaf), 3, Node(Leaf, 5, Leaf)))) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
influenced by @begeric -> https://gist.github.com/begeric/34b809ed804e649392e5