Haskell Code Katas: Counting Duplicates
Tags: haskell, codewars, kata
Published: 2021-01-04 12:47:42

---
title: Haskell Code Katas: Counting Duplicates
published: true
date: 2017-12-17 00:00:00 UTC
tags: haskell, codewars, kata
canonical_url: https://hector.dev/2017/12/17/haskell-code-katas-counting-duplicates/
---

For the past few weeks, I’ve been starting off my days with Haskell flavored code katas from [Codewars](https://www.codewars.com/). Today I started with the kata below and figured it would be a good exercise to walk through my solution.

> Write a function that will return the count of _distinct_ case-insensitive alphabetic characters and numeric digits that occur more than once in the input string. The input string can be assumed to contain only alphabets (both uppercase and lowercase) and numeric digits.

To help clarify the specifications for this kata, the [Hspec](https://hspec.github.io/) test suite is below:

```haskell
module Codwars.Kata.Duplicates.Test where

import Codwars.Kata.Duplicates (duplicateCount)
import Data.List (nub)
import Test.Hspec
import Test.QuickCheck

main = hspec $ do
  describe "duplicateCount" $ do
    it "should work for some small tests" $ do
      duplicateCount "" =?= 0
      duplicateCount "abcde" =?= 0
      duplicateCount "aabbcde" =?= 2
      duplicateCount "aaBbcde" =?= 2
      duplicateCount "Indivisibility" =?= 1
      duplicateCount "Indivisibilities" =?= 2
      duplicateCount ['a'..'z'] =?= 0
      duplicateCount (['a'..'z'] ++ ['A'..'Z']) =?= 26
    it "should work for some random lists" $ do
      property $ forAll (listOf $ elements ['a'..'z']) $ \x ->
        let xs = nub x
        in duplicateCount (concatMap (replicate 2) xs) =?= length xs
  where (=?=) = shouldBe
```

## Sorting & Grouping

To start things off, we are given the following snippet:

```haskell
module Codwars.Kata.Duplicates where

duplicateCount :: String -> Int
duplicateCount = undefined
```

My first step is to figure out how to deal with case-insensitivity. Within `Data.Char` is `toLower`, which can be used to map over each character in the input `String`.

```haskell
Prelude> x = "aaBbcde"
Prelude> x
"aaBbcde"
Prelude> import Data.Char
Prelude Data.Char> :t toLower
toLower :: Char -> Char
Prelude Data.Char> map toLower x
"aabbcde"
```

Next, I want to group like characters together. To do that, I need to `sort` and then `group` the characters together.

```haskell
Prelude Data.Char> import Data.List
Prelude Data.Char Data.List> :t sort
sort :: Ord a => [a] -> [a]
Prelude Data.Char Data.List> sort . map toLower $ x
"aabbcde"
```

The `sort` doesn’t do very much in this case because the input string was already sorted. Either way, now we can work on grouping like characters with `group`:

```haskell
Prelude Data.Char Data.List> :t group
group :: Eq a => [a] -> [[a]]
Prelude Data.Char Data.List> group . sort . map toLower $ x
["aa","bb","c","d","e"]
```

## Home Stretch

Now, how do we go from a list of `[Char]` to an `Int` length that can be used for filtering characters that only occur once? `filter`, with a `>1` condition applied to the `length`, should get us there.

```haskell
Prelude Data.Char Data.List> z = group . sort . map toLower $ x
Prelude Data.Char Data.List> filter ((>1) . length) z
["aa","bb"]
```

Here, the `.` allows us to compose `length` and `>1` together so that both can be applied to the `[Char]` provided to `filter`. The result rids the list of any characters that only occur once in the original input.

Lastly, we need the count of distinct characters from the input `String` that occur more than one, which is as simple as getting the `length` of the filtered list.

```haskell
Prelude Data.Char Data.List> f = filter ((>1) . length) z
Prelude Data.Char Data.List> length f
2
```

Putting it all together, and breaking out some of the pipelined functions into a variable in the `where` clause, we get the `duplicateCount` function below.

```haskell
module Codwars.Kata.Duplicates where

import Data.List (group, sort)
import Data.Char (toLower)

duplicateCount :: String -> Int
duplicateCount = length . filter ((>1) . length) . grouped
  where
    grouped = group . sort . map toLower
```