Practical Functional Programming - Find repeated characters | Part 1

Practical Functional Programming step by step is a series in which we are going to uncover the principles of functional programming and effective coding one small piece at the time.

Starting from a complete code example, we are going to learn step by step what makes a good functional code and what are the benefits of applying a functional programming paradigm to your codebase.

Find repeated characters

The function we are going to uncover in this first part of the series is based on the following instructions:

Given a String, find all the characters that are repeated 2 or more times and return a new String containing only these characters.

I am going to show you the solution to this assignment in three different languages: Haskell, Typescript, and Dart. We are going to learn how functional programming is used to solve the same problem in different languages.

This practical functional programming series aims to make you understand a complete functional programming function by explaining how each method works.

Haskell solution

Haskell is a pure functional programming language. It means that you are strictly required to write functional code. The solution is the following:

import Data.Map
  ( Map,
    adjust,ac
    empty,
    filter,
    insert,
    keys,
    member,
  )
import Prelude hiding (filter)

twotimes :: String -> String
twotimes str = keys $ filter (> 1) (buildmap str)
  where
    buildmap :: String -> Map Char Int
    buildmap =
      foldl
        ( \acc x ->
            if member x acc
              then adjust (+ 1) x acc
              else insert x 1 acc
        )
        empty

Typescript solution

In order to use functional programming in typescript, we are going to use the amazing fp-ts library. The solution is the following:

import * as O from 'fp-ts/Option';
import { trivial } from 'fp-ts/Ord';
import { reduce } from 'fp-ts/lib/Array';
import { pipe } from 'fp-ts/lib/function';
import { Eq as eqString } from 'fp-ts/string';
import { filter, keys, modifyAt, upsertAt } from 'fp-ts/lib/Map';

const buildmap = (str: string): Map<string, number> =>
  pipe(
    str.split(''),
    reduce(new Map<string, number>(), (acc, x) =>
      pipe(
        acc,
        modifyAt(eqString)(x, (n) => n + 1),
        O.getOrElse(() => pipe(acc, upsertAt(eqString)(x, 1)))
      )
    )
  );

const twotimes = (str: string): string =>
  pipe(
    str,
    buildmap,
    filter((n) => n > 1),
    keys(trivial),
    (strList) => strList.join('')
  );

Dart solution

Dart is not a functional language. We are going to use the fpdart library to code in dart using functional programming. The solution is the following:

import 'package:fpdart/fpdart.dart';

Map<String, int> buildmap(String str) => str.split('').foldLeft(
      <String, int>{},
      (acc, x) => {
        ...acc,
        x: (acc[x] ?? 0) + 1,
      },
    );

String twotimes(String str) => buildmap(str)
    .entries
    .where((map) => map.value > 1)
    .map((map) => map.key)
    .join('');

Take a look at the three solutions above. They may look different, but they are using the same logic to solve the same problem.

For this Part 1 of the series I am going to leave you thinking about the solutions above. Try to reason about what they are doing and see if you can recognise a pattern and understand how they work.

See you soon for Part 2!