| HN Mirror

I didn't provide an example of the flexibility for sake of brevity.

The key point I want to make with regard to flexibility is the ability to have multiple "instances" and switch between them based on run-time values.

For a trivial example, consider searching an ordered array. Let me define the typeclass:

    class Container a where
        type Item a
        size :: a -> Int
        contains :: Item a -> a -> Bool

Now consider that I have the type SortedArray that I want to make an instance of Container.

    instance Container (SortedArray a) where
        type Item (SortedArray a) = a
        size = sortedArraySize
        contains = ???

What should my `contains` be? I could linear search or I could binary search. Depending on the size of the array, either could be faster (due to cache performance and constant overheads). For small arrays, linear search could be faster, and for large arrays, binary search could be faster.

I could write my method like this:

    contains x xs = if size xs <= 64
        then linearSearch x xs
        else binarySearch x xs

But having that 64 hard coded in is sort of lame. Suppose I am writing software that will run on unknown hardware. I don't know the cache properties of it. Perhaps 16 is better. Perhaps 256. Since my application could be super high performance, I need it to be nearly optimal.

So on application start-up, I call a function which instantiates arrays of varying sizes and tries linear search vs. binary search to find the point at which one outperforms the other.

How can I use this value? I can't inject it in place of that 64 above (without unsafePerformIO...).

The solution is to instead represent the typeclass at the value level:

    data Container a b = Container
        { size :: a -> Int
        , contains :: b -> a -> Bool
        }

Now I can have code that looks like:

    main = do
        n <- findOptimalSearchSplitPoint

        let sortedArraySearch x xs = if sortedArraySize xs <= n
                then linearSearch x xs
                else binarySearch x xs
        let container = Container sortedArraySize sortedArraySearch

Then I just inject that container "instance" wherever it needs to go.