<br><br><div class="gmail_quote">On Mon, Jun 21, 2010 at 11:22 AM, Daniel Lyons <span dir="ltr">&lt;<a href="mailto:fusion@storytotell.org">fusion@storytotell.org</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Hi,<br>
<br>
I&#39;m having a little trouble figuring out precisely how to port the decision tree code from the book &quot;Programming Collective Intelligence.&quot; You can see the code here: <a href="http://code.google.com/p/memothing/source/browse/trunk/PCI/ch7/treepredict.py?r=29" target="_blank">http://code.google.com/p/memothing/source/browse/trunk/PCI/ch7/treepredict.py?r=29</a><br>

<br>
The design issue is that this code depends on dynamic typing pretty heavily. He has a table of heterogenous data. Each column has the same type, but that&#39;s implicit, not explicit. He depends on all of the values supporting &quot;==&quot;, which he uses to get a list of distinct values from each column. These values are used by the divide set function which takes a column and a value as parameters. Based on the type of the value, he chooses a different partitioning function; for strings, it&#39;s just equality again, but for numeric types he uses &gt;=. The decision tree nodes then collect not just the left and right branches but also the column number and value on which the split was performed.<br>

<br>
I have thought about this for several days and can&#39;t seem to come to a design that I like, so I&#39;m wondering how others would approach the problem. I guess you could implement it as a list of lists of some data type that is either a string or numeric, but this feels a bit like a cop-out. How would you support creating a decision tree with different types of data? I imagine possibilities using existential quantification, SYB, Data.Data and other stuff, but I don&#39;t know how to make it work. I wonder if there is an obvious functional design hiding in here that doesn&#39;t depend on any fancy stuff, but I&#39;m blinded to it by having read and understood the Python version of the code.<br>
</blockquote><div><br></div><div>Perhaps I&#39;m missing the point of your objection but I would go with the simplest design possible that works here.</div><div><br></div><div>For example, if you know you will only have numbers and strings then use something like this:</div>
<div>data Foo = N Int | S String</div><div><br></div><div>If want to leave the set of possibilities open, you could make a type class that has functions for the operations you&#39;ll want to use on the data.  Then you have at least two possibilities.</div>
<div>1. If you&#39;re okay with the collections being homogeneous then you&#39;re done.  Just make the table parameterized over your type class.</div><div>2. If you want the collections to be heterogeneous then I would try to discourage you because it will become harder to maintain and reason about your code :) Having said that, there are ways to move forward in that direction if you feel it&#39;s necessary.  It sounds like you&#39;re already aware of those solutions.</div>
<div><br></div><div>Jason</div></div>