2015 001 Correction to ListPair

Proposal 2015-001

Correction to the ListPair module

Author: John Reppy
Last revised: August 3, 2015
Status: proposed
Discussion: issue #1

---

Synopsis

The current Basis Library specification is somewhat imprecise when specifying the semantics of some of the ListPair operations with respect to the precedence of the UnequalLengths exception. For example, the Basis Library description of appEq states that

    appEq f (l1, l2)

is equivalent to

     List.app f (zipEq (l1, l2))

ignoring possible side-effects of the function f.

While the phrase "ignoring possible side-effects of the function 'f'" implies that this equivalence does not hold when f has side effects, it does not specify what the actual behavior should be.

For example, should the expression

    ListPair.appEq (fn _ => raise Fail "fail") ([1], [1, 2])

raise Fail or UnequalLengths? A direct (and efficient) implementation of ListPair.app will raise the Fail for this code.

This proposal will clarify this issue in favor of the implementation that evaluates f as it traverses the pair of lists.

Description

The descriptions of the ListPair functions appEq, mapEq, foldlEq, and foldrEq, should be replaced with the following:

• appEq f (l1, l2)
  applies the function f to the pairs of elements generated in left-to-right order from the lists l1 and l2. If the lists are of unequal lengths the exception UnequalLengths is raised. The above expression is equivalent to

      List.app f (zipEq (l1, l2))

  assuming that f is pure and terminates. Note that if the two lists are unequal in length, the UnequalLengths exception is raised after f has been applied to the preceding pairs and any effects of f have occured. For example, the following expression raises Fail, not UnequalLengths:

      ListPair.appEq (fn _ => raise Fail "fail") ([1], [1, 2])

• mapEq f (l1, l2)
  maps the function f over the pairs of elements generated in left-to-right order from the lists l1 and l2, returning the list of results. If the lists are of unequal lengths, the exception UnequalLengths is raised. The above expression is equivalent to

      List.map f (zipEq (l1, l2))

  assuming that f is pure and terminates. Note that if the two lists are unequal in length, the UnequalLengths exception is raised after f has been applied to the preceding pairs and any effects of f have occured.

• foldlEq f init (l1, l2)
  returns the result of folding the function f over the pairs of elements generated in left-to-right order from the lists l1 and l2, starting with the value init. It is equivalent to

      List.foldl (fn ((a, b), c) => f(a, b, c)) init (zipEq (l1, l2))

  assuming that f is pure and terminates. Note that if the two lists are unequal in length, the UnequalLengths exception is raised after f has been applied to the preceding pairs and any effects of f have occured.

• foldrEq f init (l1, l2)
  returns the result of folding the function f over the pairs of elements generated in right-to-left order from the lists l1 and l2, starting with the value init. It is equivalent to

      List.foldr (fn ((a, b), c) => f(a, b, c)) init (zipEq (l1, l2))

  Note that unlike the foldlEq function, the UnequalLengths exception is raised before the function f is evaluated in the situation that the lists have unequal lengths.

Discussion

Because the Eq forms of these combinators are currently specified in combination with the non-Eq forms, the language for the non-Eq forms will have to be revised to reflect the splitting of the descriptions.

Impact

This proposal follows existing practice in known SML implementations, so it should not affect any existing code.

Rationale

This proposal makes explicit the ordering of effects for these functions, which will improve consistency across implementations.

---

History

• [2015-08-22] Rewrote to be more explicit about the proposed wording changes.

• [2015-08-03] Proposed

---