Dry can cost you

· Allanderek's blog

#programming

I had an issue with a computation taking much longer than might have been expected. It turned out to be caused by a use of the function greedyGroupsOf from the list-extra library, and it was solved by writing my own, naive, implementation.

I haven't quite gotten to the bottom of why the library version of greedyGroupsOf of is so much slower than my naive version, but the reason it is slower is mostly to do with DRY or don't repeat yourself.

To see why, let's look first at my naive version:

 1greedyGroupsOf : Int -> List a -> List (List a)
 2greedyGroupsOf size elements =
 3    case elements of
 4        [] ->
 5            []
 6
 7        _ ->
 8            let
 9                ( year, remainder ) =
10                    List.splitAt size elements
11            in
12            year :: splitIntoYears size remainder

This is perfectly simple. Now, let's look at the library version:

1greedyGroupsOf : Int -> List a -> List (List a)
2greedyGroupsOf size xs =
3    greedyGroupsOfWithStep size size xs

Ah, okay, so it's just calling a more general function. This is why it is DRY, I do this kind of thing, almost habitually. Here is the implementation of the more general function:

 1greedyGroupsOfWithStep : Int -> Int -> List a -> List (List a)
 2greedyGroupsOfWithStep size step xs =
 3    let
 4        xs_ =
 5            List.drop step xs
 6
 7        okayArgs =
 8            size > 0 && step > 0
 9
10        okayXs =
11            List.length xs > 0
12    in
13    if okayArgs && okayXs then
14        List.take size xs :: greedyGroupsOfWithStep size step xs_
15
16    else
17        []

As I've mentioned I'm not entirely sure why this is so much slower than the more specific function. There is one thing it does. Because the step and the size might be different it cannot use List.splitAt and has to do two separate List.drop and List.take operations. This is because in the more general function you can have a different step size to that of the group size, a lower step size will mean that some elements are in more than one group, whilst a larger step size will mean some elements are omitted entirely.

Anyway, this means that greedyGroupsOf is slower than it needs to be, because it is a simple invocation of the more general function. In this case, it might be worth just using the specialised implementation of the function. It means repeating some code, or logic, but in this case I doubt that's so bad, these implementations are unlikely to change, and they are probably correct.