# Constructing a cumulative distribution function from a histogram

During some running process, a histogram of values shall be build up. When done, the CDF shall be derived from it and used to get the quantiles for some values.

My current implementation looks as follows:

import java.util.*
import kotlin.math.max
import kotlin.math.min
import kotlin.math.roundToInt
import kotlin.random.Random

// 10 buckets for interval [0, 1000], outliers will be clamped
class Histogram(
private val data: MutableMap<Int, Int> = mutableMapOf()
) {
val bucket = max(0, min(1000, value)) / 100
data[bucket] = data.getOrDefault(bucket, 0) + 1
}

fun deriveCDF(): CDF {
val sum = data.values.sum()
val pdfData = data.toSortedMap().mapValues { it.value.toDouble() / sum }
val cdfData: MutableMap<Int, Double> = mutableMapOf()
var acc = 0.0
pdfData.forEach {
acc += pdfData.getOrDefault(it.key, 0.0)
cdfData[it.key] = acc
}
return CDF(cdfData.toSortedMap())
}
}

// cumulative distribution function
class CDF(
private val data: SortedMap<Int, Double>
) {
fun getQuantile(value: Double): Double? {
val bucket = (10 * value).roundToInt()
return data[bucket]
}
}

fun main() {
val hist = Histogram()
List(10000) {
Random.nextInt(0, 1000)
}.forEach {
}
val cdf = hist.deriveCDF()
println(cdf.getQuantile(0.3))
}


My problem with this is, that is it possible to construct instances of CDF with SortedMaps as data that don't make sense. I would like to prevent this, already at compile time.

The obvious alternative approach is to not have the construction logic (Histogram to CDF) in a Histogram::deriveCDF, but instead have a constructor of CDF take a Histogram instance and do the math there. This however forces Histogram to expose its internals data: MutableMap<Int, Int>, i.e., make them public, for the constructor of CDF to access them. But I would like to keep this implementation detail of Histogram hidden.

How can I escape this dilemma?

• it possible to construct instances of CDF with SortedMaps as data that don't make sense. I would like to not allow this. - Have you considered doing validation in the constructor and throwing an exception? – Simon Forsberg Mar 5 '19 at 17:50
• @SimonForsberg Thanks for your suggestion. Yes, this would be possible, but I'd prefer the type system already preventing me from doing so, instead of detecting such a mistake only at runtime. – Tobias Hermann Mar 6 '19 at 7:14

val cdfData: MutableMap<Int, Double> = mutableMapOf()


This is the data that you want to your CDF class, but anyone can make a mutable map anywhere and use it for tons of things. So this is what you want to hide. So put this inside a CDFBuilder

class CDFBuilder {
private val cdfData: MutableMap = mutableMapOf<Int, Double>()

fun withData(a: Int, b: Double): CDFBuilder {
// verification and stuff
cdfData[a] = b
return this
}
}


Now, the problem is to build the CDF class without letting anyone else do it, right? There are a few options here:

1. Make a copy of the cdfData public from the CDFBuilder and read it in the CDF constructor, passing a CDFBuilder to the constructor.

Or 2, make a private constructor on the CDF-class, allowing it to only be constructed from the builder:

class CDF private constructor(val map: SortedMap<Int, Double>) {

class CDFBuilder {
private val cdfData: MutableMap = mutableMapOf<Int, Double>()

fun withData(a: Int, b: Double): CDFBuilder {
// verification and stuff
cdfData[a] = b
return this
}

fun build(): CDF {
return CDF(map.toSortedMap())
}
}
}

• Thanks a lot for the idea. It looked good at the beginning, but if I understand correctly, it does not solve the actual problem. Now still anybody can just build invalid CDFs from somewhere without providing a Histogram, because one can just instantiate a CDF.CDFBuilder() and put some values in it, as shown in this snippet: gist.github.com/Dobiasd/6cc56e940f3b135dd9f6f04cb53c4ce2 Or am I missing something? – Tobias Hermann Mar 6 '19 at 20:19
• @TobiasHermann Well, I was thinking that you would have validation in your build() method, or in the addData. But if you have the requirement to have a Histogram and not just data that also makes a valid Histogram then you could use the same trick by having your Histogram have access to the CDL's private constructor. Or have Histogram and CDL be in the same package and not have anything else in the same package, and have the CDL have a package-scoped constructor. – Simon Forsberg Mar 6 '19 at 21:55
• Ah, thanks. I understand the package-scoped constructor, and I like the idea. But you also wrote "having your Histogram have access to the CDL's private constructor", which spikes my interest. But I don't yet understand how to implement this. Could you show me? – Tobias Hermann Mar 7 '19 at 6:21
• @TobiasHermann Make Histogram the inner class and CDF the outer class, similar to CDF and CDFBuilder in my answer. – Simon Forsberg Mar 7 '19 at 11:56
• Thanks again. A solution using nested/inner classes seems best to me. For completeness, it's also possible to make Histogram the outer class and CDF the nested class, like this. – Tobias Hermann Mar 7 '19 at 13:05

One possible solution (thanks a lot again to Simon Forsberg) is to nest CDF into Histogram:

import java.util.*
import kotlin.math.max
import kotlin.math.min
import kotlin.math.roundToInt
import kotlin.random.Random

// 10 buckets for interval [0, 1000], outliers will be clamped
class Histogram {
private val data: MutableMap<Int, Int> = mutableMapOf()
val bucket = max(0, min(1000, value)) / 100
data[bucket] = data.getOrDefault(bucket, 0) + 1
}

// cumulative distribution function
class CDF(
histogram: Histogram
) {
private val data: SortedMap<Int, Double> = deriveCDFData(histogram)
fun getQuantile(value: Double): Double? {
val bucket = (10 * value).roundToInt()
return data[bucket]
}

private fun deriveCDFData(histogram: Histogram): SortedMap<Int, Double> {
val data = histogram.data
val sum = data.values.sum()
val pdfData = data.toSortedMap().mapValues { it.value.toDouble() / sum }
val cdfData: MutableMap<Int, Double> = mutableMapOf()
var acc = 0.0
pdfData.forEach {
acc += pdfData.getOrDefault(it.key, 0.0)
cdfData[it.key] = acc
}
return cdfData.toSortedMap()
}
}
}

fun main() {
val hist = Histogram()
List(10000) {
Random.nextInt(0, 1000)
}.forEach {