DecisionTrees.hs

buildTreeAtLevel :: (Examples -> Double)
                 -> PB.SplittingConstraints
                 -> Int
                 -> Examples
                 -> DecisionTree
buildTreeAtLevel leafWeight splittingConstraints level examples =
    if shouldSplit splittingConstraints level examples bestSplit
    then Branch { _feature=_splitFeature bestSplit
                , _value=_splitValue bestSplit
                , _left=recur leftExamples
                , _right=recur rightExamples
                }
    else Leaf {_value=leafWeight examples} where
        -- candidate splits
        candidates =
            V.map (findBestSplit examples) (getFeatures examples)
        -- best candidate from all the features
        bestSplit =
            V.maximumBy (compare `on` _averageGain) candidates
        -- sort the examples at this branch by the best feature
        orderedExamples =
            sortFeature examples (_splitFeature bestSplit)
        -- left branch takes <, right branch takes >
        branchLeft ex =
            (features' ex ! _splitFeature bestSplit) <
               _splitValue bestSplit
        -- construct the next level of the tree
        recur =
            buildTreeAtLevel leafWeight splittingConstraints (level + 1)
        leftExamples = V.takeWhile branchLeft orderedExamples
        rightExamples = V.dropWhile branchLeft orderedExamples