[m-rev.] for post-commit review: organize array.m, bt_array.m and pprint.m

[Julien Fischer]

On Thu, 9 Jun 2022, Zoltan Somogyi wrote:

> Carve stdlib module ra_list.m out of bt_array.m.

...

> diff --git a/library/ra_list.m b/library/ra_list.m
> index e69de29bb..23f9f214a 100644
> --- a/library/ra_list.m
> +++ b/library/ra_list.m
> @@ -0,0 +1,321 @@
> +%---------------------------------------------------------------------------%
> +% vim: ft=mercury ts=4 sw=4 et
> +%---------------------------------------------------------------------------%
> +% Copyright (C) 1997,2000,2003,2005-2006 The University of Melbourne.
> +% Copyright (C) 2014-2015,2021-2022 The Mercury team.
> +% This file is distributed under the terms specified in COPYING.LIB.
> +%---------------------------------------------------------------------------%
> +%
> +% File: ra_list.m
> +% Main author: bromage.
> +% Stability: medium-low
> +%
> +% This module implements `random access lists', or ra_lists for short.
> +% It is very similar to a list data type, and it supports O(1) head/tail/cons
> +% operations, but it also supports O(log n) lookup and update.
> +% The representation is a list of perfectly balanced binary trees.
> +%
> +% For more details on the implementation:
> +%
> +%   Chris Okasaki, "Purely Functional Random-Access Lists".
> +%   Functional Programming Languages and Computer Architecture,
> +%   June 1995, pp 86-95.
> +%
> +%---------------------------------------------------------------------------%
> +
> +:- module ra_list.
> +:- interface.
> +
> +:- import_module list.
> +
> +:- type ra_list(T).
> +
> +%---------------------------------------------------------------------------%
> +%
> +% Constructing ra_lists.
> +%

I would not prefix the names of all the operations in this module with "ra_list_".
It makes the names unwieldy and also complicates swapping between ra_lists and
other sequence types such as cords or standard lists.

> +
> +    % Return an empty random access list.
> +    %
> +:- pred ra_list_nil(ra_list(T)::uo) is det.

For consistency with elsewhere, I suggest you call this init.

> +
> +    % Return an random access list with the given head and tail.
> +    %
> +:- pred ra_list_cons(T::in, ra_list(T)::in, ra_list(T)::out) is det.

This module lacks many of the standard operations I would expect to exist on a
container style data structure.  Some of these can be added as required, but
the following should be added now:

    - is_empty / is_not_empty
    - singleton
    - is_singleton
    - length
    - foldl
    - foldr
    - map

> +%---------------------------------------------------------------------------%
> +%
> +% Deconstructing ra_lists.
> +%
> +
> +    % Return the head of the given random access list.
> +    % Fail if it is empty.
> +    %
> +:- pred ra_list_head(ra_list(T)::in, T::out) is semidet.

This is a function in the list module (it probably shouldn't be) and is named
get_first in the cord module.

> +    % Return the tail of the given random access list.
> +    % Fail if it is empty.
> +    %
> +:- pred ra_list_tail(ra_list(T)::in, ra_list(T)::out) is semidet.
> +
> +    % Return the head and the tail of the given random access list.
> +    % Fail if it is empty.
> +    %
> +:- pred ra_list_head_tail(ra_list(T)::in, T::out, ra_list(T)::out) is semidet.
> +
> +%---------------------------------------------------------------------------%
> +%
> +% Random access on ra_lists.
> +%
> +
> +    % Return the item at the given index in the given random access list.
> +    % The first element is at index 0.
> +    %
> +    % Fail if the list is not long enough to have an element
> +    % at the given index.
> +    %
> +:- pred ra_list_search(ra_list(T)::in, int::in, T::out) is semidet.
> +
> +    % Return the item at the given index in the given random access list.
> +    % The first element is at index 0.
> +    %
> +    % Fail if the list is not long enough to have an element
> +    % at the given index.
> +    %
> +:- pred ra_list_lookup(ra_list(T)::in, int::in, T::out) is det.

The names of these operations differ from the corresponding ones in the list module.
(That module also offers both zero- and one-based indexing.)

The diff is otherwise fine.

Julien.