Using map and fold to generate a list of strings

The goal of this tutorial is to generate a YAML list of test names, such as:

- test-variantA-suffixA
- test-variantA-suffixB
- test-variantB-suffixA
- test-variantB-suffixB

We’ll use the dhall and dhall-to-yaml command line, make sure to follow the install instructions from the getting started tutorial.

Map

We would like to begin by prepending the same prefix to a list of suffixes, so that our final code looks like this:

generate-test-name "variantA" [ "suffixA", "suffixB" ]

= [ "variantA-suffixA", "variantA-suffixB" ]

… but in order to do so we need a way to apply the same transformation (e.g. append a suffix) to each element of a list.

The “map” higher-order function provides precisely this capability: we can use map to uniformly transform each element of a list, like this:

-- ./string-matrix.dhall

let List/map =
      https://prelude.dhall-lang.org/v11.1.0/List/map sha256:dd845ffb4568d40327f2a817eb42d1c6138b929ca758d50bc33112ef3c885680

let generate-test-name =
      \(prefix : Text) ->
        List/map Text Text (\(suffix : Text) -> "${prefix}-${suffix}")

in  generate-test-name "variantA" [ "suffixA", "suffixB" ]

$ dhall --file ./string-matrix.dhall
[ "variantA-suffixA", "variantA-suffixB" ]

$ dhall-to-yaml --file ./string-matrix.dhall
- variantA-suffixA
- variantA-suffixB

In dhall, generic functions such as map require types to be explicitly specified as function arguments. The map signature is:

let map : forall (a : Type) -> forall (b : Type) -> (a -> b) -> List a -> List b

In other words, the map arguments are:

input type (a),
output type (b),
a function that goes from a to b,
a list of a, and
it returns a list of b.

Functions can be partially saturated as each argument evaluates to a new function. This technique is called currying. For example, the type of the List/map function changes with each new argument:

List/map
    : forall (a : Type) -> forall (b : Type) -> (a -> b) -> List a -> List b

List/map Text
    : forall (b : Type) -> (Text -> b) -> List Text -> List b

List/map Text Text
    : (Text -> Text) -> List Text -> List Text

List/map Text Text (\(prefix : Text) -> "${prefix}-${suffix}")
    : List Text -> List Text

Thus, generate-test-name pre-applies the map function from Text to Text using a known prefix. Then it is given a list of suffixes to generate new strings.

Nested map

We would like to prepend a list of prefixes to a list of suffixes, so that our final code looks like this:

generate-test-suite [ "variantA", "variantB" ] [ "suffixA", "suffixB" ]

= [ "variantA-suffixA", "variantA-suffixB", "variantB-suffixA", "variantB-suffixB" ]

To do so we can call two maps and generate our initial goal by adding the following generate-test-suite function to our ./string-matrix.dhall file:

-- ./string-matrix.dhall

let List/map =
      https://prelude.dhall-lang.org/v11.1.0/List/map sha256:dd845ffb4568d40327f2a817eb42d1c6138b929ca758d50bc33112ef3c885680

let generate-test-name =
      \(prefix : Text) ->
        List/map Text Text (\(suffix : Text) -> "${prefix}-${suffix}")

let generate-test-suite =
      \(prefixes : List Text) ->
      \(suffixes : List Text) ->
        List/map
          Text
          (List Text)
          (\(prefix : Text) -> generate-test-name prefix suffixes)
          prefixes

in  generate-test-suite [ "variantA", "variantB" ] [ "suffixA", "suffixB" ]

$ dhall --file ./string-matrix.dhall
[ [ "variantA-suffixA", "variantA-suffixB" ]
, [ "variantB-suffixA", "variantB-suffixB" ]
]

$ dhall-to-yaml --file ./string-matrix.dhall
- - variantA-suffixA
  - variantA-suffixB
- - variantB-suffixA
  - variantB-suffixB

However, by doing so we get a value of type List (List Text) (i.e. a List of Lists of Text). So we can get a flat list by using the fold function.

Folding a list of list of texts to a flat list of text

We would like the generate-test-suite function to produce a flat list of test names. To do so we need a way to combine each element of the list.

The “fold” higher-order function provides precisely this capability: we can use fold to reduce a list of objects to another type. Its signature is:

let fold
    :   forall (a : Type)
      → List a
      → forall (list : Type)
      → forall (cons : a → list → list)
      → forall (nil : list)
      → list

In other words, the fold arguments are:

input type (a),
the list to fold (a List of a),
output type (b),
a folding function that goes from (a, b) to b,
a starting value of type b, and
it returns a b.

Therefore, we can implement a flatten-list-text function like so:

-- ./concat-example.dhall
let {- Convert [[a, b], [c, d]] to [a, b, c, d] -}
    flatten-list-text =
      \(to-fold : List (List Text)) ->
          List/fold
            (List Text)
            to-fold
            (List Text)
            (\(a : List Text) -> \(b : List Text) -> a # b)
            ([] : List Text)
        : List Text

let example =
      \(a : Text) ->
      \(b : Text) ->
      \(c : Text) ->
      \(d : Text) ->
        assert : flatten-list-text [ [ a, b ], [ c, d ] ] === [ a, b, c, d ]

in  flatten-list-text [ [ "A", "B" ], [ "C", "D" ] ]

$ dhall-to-yaml --file ./concat-example.dhall
- A
- B
- C
- D

NOTE: This function can also be defined as:
let flatten-list-text = https://prelude.dhall-lang.org/List/concat Text

We can use this new function in our previous example:

in flatten-list-text
     (generate-test-suite [ "suffixA", "suffixB" ] [ "variantA", "variantB" ])

- variantA-suffixA
- variantA-suffixB
- variantB-suffixA
- variantB-suffixB

Refactoring the generate-test-suite function

We would like the generate-test-suite function to return the correct type instead of having to use flatten-list-text manually.

The flatten-list-text function doesn’t have to be a top-level function and the generate-test-suite could automatically fold the result. Let’s rewrite the above example using nested let:

-- ./string-matrix.dhall
let List/map =
      https://prelude.dhall-lang.org/v11.1.0/List/map sha256:dd845ffb4568d40327f2a817eb42d1c6138b929ca758d50bc33112ef3c885680

let generate-test-name =
      \(prefix : Text) ->
        List/map Text Text (\(suffix : Text) -> "${prefix}-${suffix}")

let generate-test-suite =
      \(prefixes : List Text) ->
      \(suffixes : List Text) ->
        let flatten-list-text = https://prelude.dhall-lang.org/List/concat Text

        in  flatten-list-text
              ( List/map
                  Text
                  (List Text)
                  (\(prefix : Text) -> generate-test-name prefix suffixes)
                  prefixes
              )

in  generate-test-suite [ "variantA", "variantB" ] [ "suffixA", "suffixB" ]

This is equivalent to the previous evaluation, but the flatten-list-text function is now hidden in the generate-test-suite thanks to a nested let.

We could use the new function to generate even more variations:

in  generate-test-suite
      ( generate-test-suite
          (generate-test-suite [ "tox" ] [ "py27", "py38" ])
          [ "postgresql", "sqlite" ]
      )
      [ "el6", "el7" ]

- tox-py27-postgresql-el6
- tox-py27-postgresql-el7
- tox-py27-sqlite-el6
- tox-py27-sqlite-el7
- tox-py38-postgresql-el6
- tox-py38-postgresql-el7
- tox-py38-sqlite-el6
- tox-py38-sqlite-el7

Generalizing the string matrix generation

While the above is working, the code can be improved to remove repetitive function calls. We would like our final code to look like this:

generate-test-matrix [ [ "tox" ], ["py27", "py38"], ["postgresql", "sqlite"] ]

= [ "tox-py27-postgresql", "tox-py38-postgresql", "tox-py27-sqlite", ...]

… but in order to do so we need to generalize our function.

The fold documentation actually mentions:

If you treat the list [ x, y, z ] as cons x (cons y (cons z nil)), then a fold just replaces each cons and nil with something else.

This is exactly what we need, cons is our generate-test-suite and nil is the initial suffix [ "el6", "el7" ]!

-- ./string-matrix.dhall
let List/map =
      https://prelude.dhall-lang.org/v11.1.0/List/map sha256:dd845ffb4568d40327f2a817eb42d1c6138b929ca758d50bc33112ef3c885680

let generate-test-name =
      \(prefix : Text) ->
        List/map Text Text (\(suffix : Text) -> "${prefix}-${suffix}")

let generate-test-suite =
      \(prefixes : List Text) ->
      \(suffixes : List Text) ->
        let flatten-list-text = https://prelude.dhall-lang.org/List/concat Text

        in  flatten-list-text
              ( List/map
                  Text
                  (List Text)
                  (\(prefix : Text) -> generate-test-name prefix suffixes)
                  prefixes
              )

let generate-test-matrix =
      \(variations : List (List Text)) ->
      \(last : List Text) ->
        List/fold (List Text) variations (List Text) generate-test-suite last

in  generate-test-matrix
      [ [ "tox" ], [ "py27", "py38" ], [ "postgresql", "sqlite" ] ]
      [ "el6", "el7" ]

- tox-py27-postgresql-el6
- tox-py38-postgresql-el6
- tox-py27-sqlite-el6
- tox-py38-sqlite-el6
- tox-py27-postgresql-el7
- tox-py38-postgresql-el7
- tox-py27-sqlite-el7
- tox-py38-sqlite-el7

Note: Using the List/head function the generate-test-matrix could be improved to take a single list of argument.