2015 003b List

structure List : LIST

The largest number of proposed additions is to the List module. Lists play a key role in many SML programs, but there are a number of common usage patterns that are not directly supported by the Basis Library. These include adding indexed forms of the list combinators, fused combinators, and a couple of utility functions. The new indexed functions follow the pattern of similar functions in other modules and place the index as the first argument.

This page is part of proposal 2015-003.

---

Synopsis

val unfoldl        : ('strm -> ('a * 'strm) option) -> 'strm -> 'a list
val unfoldr        : ('strm -> ('a * 'strm) option) -> 'strm -> 'a list

val reduce         : ('a * 'a -> 'a) -> 'a -> 'a list -> 'a

val appi           : (int * 'a -> unit) -> 'a list -> unit
val mapi           : (int * 'a -> 'b) -> 'a list -> 'b list
val mapPartiali    : (int * 'a -> 'b option) -> 'a list -> 'b list
val foldli         : (int * 'a * 'b -> 'b) -> 'b -> 'a list -> 'b
val foldri         : (int * 'a * 'b -> 'b) -> 'b -> 'a list -> 'b
val findi          : (int * 'a -> bool) -> 'a list -> (int * 'a) option

val revMap         : ('a -> 'b) -> 'a list -> 'b list
val revMapi        : (int * 'a -> 'b) -> 'a list -> 'b list
val revMapPartial  : ('a -> 'b option) -> 'a list -> 'b list
val revMapPartiali : (int * 'a -> 'b option) -> 'a list -> 'b list

val concatMap      : ('a -> 'b list) -> 'a list -> 'b list
val concatMapi     : (int * 'a -> 'b list) -> 'a list -> 'b list

val foldMapl       : ('b * 'c -> 'c) -> ('a -> 'b) -> 'c -> 'a list -> 'c
val foldMapr       : ('b * 'c -> 'c) -> ('a -> 'b) -> 'c -> 'a list -> 'c

val splitAt        : 'a list * int -> 'a list * 'a list

val update         : 'a list * int * 'a -> 'a list
val sub            : 'a list * int -> 'a

Description

• unfoldl get strm

creates a list by successive calls to `get` on the functional stream `strm` until the stream terminates (_i.e._, `get` returns `NONE`). The resulting list is in left-to-right order; _i.e._, the head of the list is the first stream element. Note that the first argument matches the `StringCvt.reader` type definition.

• unfoldr get strm

creates a list by successive calls to `get` on the functional stream `strm` until the stream terminates (_i.e._, `get` returns `NONE`). The resulting list is in right-to-left order; _i.e._, the last element of the list is the first stream element. Note that the first argument matches the `StringCvt.reader` type definition.

• reduce f id xs

Applies the reduction operation `f` to the elements of the list in left-to-right order. If the list is empty, then `id` is returned (typically the _right identity_ of `f`). This function can be defined in terms of `foldl`: ```sml fun reduce f id [] = id | reduce f _ (x::xs) = foldl f x xs ```

• appi f l

Like `app`, this function applies the function `f` to the elements of `l` from left to right, but it also supplies `f` with the index of the corresponding element.

• mapi f l

Like `map`, this function applies `f` to each element of `l` from left to right, returning the list of results, but it also supplies `f` with the index of the corresponding element.

• mapPartiali f l

Like `mapPartial`, this function applies `f` to each element of `l` from left to right, returning those results that were wrapped in `SOME`, but it also supplies `f` with the index of the corresponding element. The above expression is equivalent to ```sml ((map valOf) o (filter isSome) o (mapi f)) l ```

• foldli f init l

Like `foldl`, this function reduces the list `l` by applying the reduction operator `f` from left to right, but it also supplies `f` with the corresponding index of the element.

• foldri f init l

Like `foldr`, this function reduces the list `l` by applying the reduction operator `f` from right to left, but it also supplies `f` with the corresponding index of the element. Note that the index specifies the index of the element in `l`.

• findi pred l

Like `find`, this function scans the lsit `l` from left to right looking for the first element that satisfies the predicate, but it also supplies `pred` with the corresponding index of the element and, upon finding a satisfying element, it returns a pair of the element's index and the element.

• revMap f l

is equivalent to the expression `rev (map f l)`

• revMapi f l

is equivalent to the expression `rev (mapi f l)`

• revMapPartial f l

is equivalent to the expression `rev (mapPartial f l)`

• revMapPartiali f l

is equivalent to the expression `rev (mapPartiali f l)`

• concatMap f l

is equivalent to the expression `concat (map f l)`

• concatMapi f l

is equivalent to the expression `concat (mapi f l)`

• foldMapl rf mf init l

reduces the list `l` from left to right by applying the fusion of the reduction function `rf` and the mapping function `mf`. The expression is equivalent to ```sml foldl (fn (x, acc) => rf (mf x, acc)) init l ```

• foldMapr rf mf init l

reduces the list `l` from right to left by applying the fusion of the reduction function `rf` and the mapping function `mf`. The expression is equivalent to ```sml foldr (fn (x, acc) => rf (mf x, acc)) init l ```

• splitAt l n

Splits the list `l` into two pieces, with the first list having `n` elements. Raises the `Subscript` exception if `i` is out of bounds.

• update l i x

returns a list that is the same as `l`, except that the ``i``th element has been replaced with the value `x`. Raises the `Subscript` exception if `i` is out of bounds.

• sub (l, i)

returns the ``i``th element of the list `l`. This function is an alias for `List.nth`, and is included to help make the `List` and `Vector` modules more compatible.

Discussion

The motivation for the reduce function is for when the reduction operator is relatively expensive and thus avoiding an extra call is beneficial. We do not supply a right-to-left form, because the natural definition ends up being equivalent to foldr.

Matthew Fluet proposes an alternative design for the foldMap functions

val foldMapl : ('a * 'c -> 'b * 'c) -> 'c -> 'a list -> ('b list * 'c)
val foldMapr : ('a * 'c -> 'b * 'c) -> 'c -> 'a list -> ('b list * 'c)

These take a function that combines mapping (from type 'a to 'b) with reduction (to type 'c), and return both the result of the mapping and the reduction. They have the following reference implementations:

fun foldMapl f init xs = let
      fun f' (x, (ys, r)) = let val (y, r) = f(x, r) in (y::ys, r) end
      val (ys, r) = List.foldl f' ([], init) xs
      in
	(List.rev ys, r)
      end

fun foldMapr f init xs = let
      fun f' (x, (ys, r)) = let val (y, r) = f(x, r) in (y::ys, r) end
      val (ys, r) = List.foldl f' ([], init) xs
      in
	(ys, r)
      end

Perhaps we should support both versions.

There might be an argument to include indexed versions of the fused fold-map functions with the following types:

val foldMapli	: ('b * 'c -> 'c) -> (int * 'a -> 'b) -> 'c -> 'a list -> 'c
val foldMapri	: ('b * 'c -> 'c) -> (int * 'a -> 'b) -> 'c -> 'a list -> 'c

but since I cannot think of any obvious use cases, I recommend that we omit them from the Basis Library for the time being.

Rationale

These extensions support a number of common SML usage patterns that are not directly supported by the Basis Library, such as indexed combinators and fused combinators. The splitAt function combines the functions of take and drop as a way to partition a list. The sub and update functions are added to make the LIST and VECTOR signatures more compatible (note that sub is an alias for nth).