improvements for Tree

[Jeffrey Shaw]

I've been using the Tree class today, and I see some room for improvement. One is that construction and pattern matching should more like conventional Scala case classes, and the other is that there needs to be an equals implementation.

There should be symmetry between the constructors Tree.leaf, Tree.node and the pattern matching, which right now is gotten by Tree.Node. If we really can't have a concrete case class, Scala convention calls for constructors Tree.Leaf.apply, Tree.Node.apply, and corresponding unapply methods in the same objects.

Equality doesn't work the way I would expect. Having an Equal instance is perfectly great, but it needs to be in addition to the conventional equals method, not instead of. I'm running unit tests on trees, and requiring that I use Equal makes them unnecessarily horrible to write. The following fails, even though the trees are the same.

assertResult(Tree.leaf("hi"))(Tree.leaf("hi"))

Instead, I have to invoke special scalaz magic.

assert(Equal[Tree[String]].equal(Tree.leaf("hi"), Tree.leaf("hi")))

I would also like to improve toString, but I see that is probably impossible with the level of laziness Tree is using.

I'll see about making a merge request with some changes unless people really dislike my ideas.

Jeff

[Robert Norris]

Hi Jeffrey,

Node is the only constructor; leaf is just a convenience for a node with no children. As such any match on a tree can be done in terms of Node; if you wish to match a leaf you can just use Node(data, Stream.empty) as the pattern.

As for universal equals (as defined on Any) we avoid this in scalaz because the claim that all types have a sensible and consistent definition of equality is simply false. So as you discovered, equality for Tree is defined in terms of an instance of the Equal typeclass, which is available if such an instance exists for the label type. Scalaz provides syntax to make this easy to invoke:

scala> "hi".leaf === "hi".leaf

res8: Boolean = true

For printing trees we have the draw and drawTree methods, which rely on a Show instance for the label type.

scala> val t = "animals".node("mammals".node("monkey".leaf, "cat".leaf), "reptiles".node("lizard".leaf))

t: scalaz.Tree[String] = <tree>

scala> t.draw.foreach(println)

"animals"

|

+- "mammals"

|  |

|  +- "monkey"

|  |

|  `- "cat"

|

`- "reptiles"

   |

   `- "lizard"

Hope this helps. Note that the #scalaz IRC channel on FreeNode is a good place to discuss questions or ideas if you don't get the answers you need here.

rob / @tpolecat

--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scalaz+un...@googlegroups.com.
To post to this group, send email to sca...@googlegroups.com.
Visit this group at http://groups.google.com/group/scalaz.
For more options, visit https://groups.google.com/d/optout.

[Tony Morris]

Also, as to the test, where you'd prefer this:

assertResult(Tree.leaf("hi"))(Tree.leaf("hi"))

but you have to do this:

assert(Equal[Tree[String]].equal(Tree.leaf("hi"), Tree.leaf("hi")))

The penalty for the former is loss of safety, while for the latter, it
is apparent unnecessary labour. Unfortunately, some test frameworks rely
on Object#equals. Repair this with:

def assertResult[A](a1: A)(a2: A)(implicit E: Equal[A]) =
assert(E.equal(a1, a2))

Now you have the benefit of both.

>> <mailto:scalaz+un...@googlegroups.com>.

>> To post to this group, send email to sca...@googlegroups.com

>> <mailto:sca...@googlegroups.com>.

>> Visit this group at http://groups.google.com/group/scalaz.
>> For more options, visit https://groups.google.com/d/optout.
>

> --
> You received this message because you are subscribed to the Google
> Groups "scalaz" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to scalaz+un...@googlegroups.com

> <mailto:scalaz+un...@googlegroups.com>.

> To post to this group, send email to sca...@googlegroups.com

> <mailto:sca...@googlegroups.com>.

[Jeffrey Shaw]

Hi Rob,

You are right that you can pattern match with Node, but the constructor is node with the lowercase 'n'. I found this to be somewhat confusing. At least, I don't see one with an uppercase 'n'.

I like the postfix leaf method you showed me. I see there's a node one, too.

The === for Equal is very good, but ScalaTest defines their own === which is much like scalaz's. I had to use some other syntax.

Jeff

[Jeffrey Shaw]

Tony, thanks for the alternate definition of assertResult. I will try it.

Jeff