xlist
x  List
xlist
normalize-xlist-type
1 Splitting an xlist in its constituent sublists
split-xlist
2 Untyped versions of xlist
xlist
3 Special identifiers recognised by xlist
^
once
6.12

xlist

Georges Dupéron <[email protected]>

 (require xlist) package: xlist

Fancy lists, with bounded or unbounded repetition of elements. Can be used as a type or match pattern.

To use the type expander, you must first require the type-expander library.

type-expander

(xList τᵢ ...)
(xList τᵢ ... . rest)
(xList τᵢ ... #:rest rest)

type-expander

(xlist τᵢ ...)
(xlist τᵢ ... . rest)
(xlist τᵢ ... #:rest rest)
 
τᵢ = type
  | repeated-type
     
repeated-type = type ^ repeat
  | type ^ {repeat}
  | type {repeat}
  | type superscripted-repeat
  | type *
  | type +
  | superscripted-id
     
repeat = once
  | nat
  | nat +
  | +
  | nat - nat
  | nat - 
  | nat -
  | - nat
  | -
  | - 
  | *
 
  nat : (syntax/c exact-nonnegative-integer?)
The notation type ^ n, where n is a number, indicates that the given type should be repeated n times within the list. Therefore, the following two types are equivalent:

(xList Number ^ 3 Symbol String ^ 2)
 
(List Number Number Number Symbol String String)

The notation type * indicates that the given type may be repeated zero or more times. Therefore, the following two types are equivalent:

(xList Number * Symbol String *)
 
(Rec R1 (U (Pairof Number R1)
           (List* Symbol (Rec R2 (U (Pairof String R2)
                                    Null)))))

The notation type ^ n + indicates that the given type may be repeated n or more times. Therefore, the following two types are equivalent:

(xList Number ^ {2 +} String)
 
(List* Number Number (Rec R1 (U (Pairof Number R1)
                                (List String))))

When the number preceding + is omitted, it defaults to 1.

The notation type ^ once yields the same type as type ^ 1, but other forms recognise once and treat it specially. For example, xlist-split splits the corresponding element as a standalone value, not as a list of length one.

The notation type ^ n - m indicates that the given type may be repeated between n (inclusive) and m (inclusive) times. Therefore, the following two types are equivalent:

(xList Number ^ {2 - 5} String)
 
(U (List Number Number String)
   (List Number Number Number String)
   (List Number Number Number Number String)
   (List Number Number Number Number Number String))

Be aware that the tail of the xList following the use of type ^ n - m is repeated n - m times, so if the tail itself contains uses of -, the resulting macro-expanded type will be huge, and may easily make Typed/Racket run out of memory, or slow down the type checking.

If the first bound is omitted, it defaults to 0, and if the second bound is omitted, it defaults to . This means that - on its own is equivalent to *, but the latter form is preferred.

The superscripted-repeat is a representation of repeat using superscripted unicode characters, without spaces (i.e. the superscripted-repeat is a single identifier):

A superscripted-id is a type identifier ending with a sequence of characters which would otherwise be valid for superscripted-repeat. In other words, if the type is an identifier, the type and the superscripted-repeat can be coalesced into a single identifier.

The identifier String3 is equivalent to the notations String 3 (with a space between the identifier and the 3) and String ^ 3.

Similarly, the identifier String* is equivalent to the notations String * (with a space between the identifier and the *), String ^ * (using a regular asterisk, i.e. the multiplication function in Racket) and String * (using a regular asterisk, i.e. the multiplication function in Racket).

The same logic applies to the other cases.

match-expander

(xlist patᵢ ...)
(xlist patᵢ ... . rest)
(xlist patᵢ ... #:rest rest)
 
patᵢ = pattern-or-spliced
  | repeated-pattern
  | spliced-pattern
     
pattern-or-spliced = pattern
  | spliced-pattern
     
spliced-pattern = ,@pattern
     
repeated-pattern = pattern-or-spliced ^ repeat
  | pattern-or-spliced ^ {repeat}
  | pattern-or-spliced superscripted-repeat
  | pattern-or-spliced *
  | pattern-or-spliced +
  | pattern-or-spliced ooo
  | superscripted-id
     
repeat = once
  | nat
  | nat +
  | +
  | nat - nat
  | nat - 
  | nat -
  | - nat
  | - 
  | -
  | *
  | ooo
     
ooo = ...
  | ..k
  | ___
  | __k
  | ...+
 
  nat : (syntax/c exact-nonnegative-integer?)
This match expander works like the xList type expander, but instead controls the repetition of match patterns. The repeated patterns are not literally copied, as this would likely cause errors related to duplicate attributes. Instead, the repeat forms control the number of times a pattern may be bound, like ... does.

If the repeat is once, or if the pattern does not have a repeat, then the pattern is not put under ellipses, so that (match '(42) [(xlist a ^ once) a]) returns 42, whereas (match '(42) [(xlist a ^ 1) a]) returns '(42).

For convenience and compatibility with existing match patterns, the following equivalences are provided:
  • ... is equivalent to *

  • ..k is equivalent to k +

  • ___ is equivalent to *

  • __k is equivalent to k +

  • ...+ is equivalent to +

Additionally, when #,@pattern appears as one of the xlist elements, the given pattern may match any number of elements in the list. This is implemented in terms of append from the match-string library.

The following two match patterns are therefore equivalent:

(xlist number?3 - 5 ,@(list-no-order number? string?) symbol?+)
 
(append (and (list number? ...) (app length (? (between/c 3 5))))
        (list-no-order number? string?)
        (list symbol? ..1))

Applying a repeat indicator on a splice is not supported yet, i.e. (xlist ,@(list-no-order number? string?) 5) will not work.

Note : Typed/Racket’s type inference is not strong enough (yet) to support some match patterns, and there is no typed/match library which would help with that (yet). This means that although by construction xlist tries to avoid generating such patterns, a few of the patterns supported by xlist will not work in typed/racket (rest values and spliced lists are the most likely to cause problems). As an alternative, try the split-xlist pattern, which produces code which should propagate type information to the different sub-lists.

procedure

(normalize-xlist-type stx context)  syntax?

  stx : syntax?
  context : syntax?
Normalizes the xlist type. The normalized form has one type followed by ^ followed by a repeat within braces (a type without a repeat is transformed into type ^ {once}) for each position in the original type. It always finishes with #:rest rest-type. This function also performs a few simplifications on the type, like transforming ^ {3 -} into ^ {3 +}, and transforming ^ {0 -} into ^ {*}.

1 Splitting an xlist in its constituent sublists

match-expander

(split-xlist pat τᵢ ...)

(split-xlist pat τᵢ ... . rest)
(split-xlist pat τᵢ ... #:rest rest)
 
τᵢ = type
  | repeated-type
     
repeated-type = type ^ repeat
  | type ^ {repeat}
  | type {repeat}
  | type superscripted-repeat
  | type *
  | type +
  | superscripted-id
     
repeat = once
  | nat
  | nat +
  | +
  | nat - nat
  | nat - 
  | nat -
  | - nat
  | -
  | - 
  | *
 
  nat : (syntax/c exact-nonnegative-integer?)
This match pattern splits an xlist into a list of lists, and matches the result against pat. Each repeated element of the xlist is extracted into one of these sublists. The type for each sublist is determined based on the element’s type and its repeat:
  • If the repeat for that element is once, then the element is inserted directly, without nesting it within a sublist. In contrast, it the repeat were 1, the element would be inserted in a sublist of length one.

  • If the repeat for that element is * or an equivalent, the type of the sublist will be (Listof type)

  • If the repeat for that element is n + or an equivalent, the type of the sublist will be (xList type ^ n +)

  • If the repeat for that element is n or an equivalent, the type of the sublist will be (xList type ^ n)

  • If the repeat for that element is from - to or an equivalent, the type of the sublist will be (xList type ^ from - to)

  • The #:rest or dotted rest is included as the last element of the list matched against pat. If the first form without a rest type is used, the list matched against pat still contains '() as a last element:

    Example:
    > (match '(1 2 3)
        [(split-xlist (list (list a) (list b c) (? null?))
                      Number¹ Number⃰)
         (vector c b a)])

    - : (Vector Number Number Integer)

    '#(3 2 1)

Note that split-xlist assumes the value it is matched against has the type (xlist τᵢ ... maybe-rest), but does not apply (? (make-predicate (xlist τᵢ ... maybe-rest))) to the value itself. The rationale is that the make-predicate may fail at compile-time if it cannot generate a contract for the given type. In some cases, however split-xlist will still manage to successfully generate the match pattern, and can be used on its own, provided that the value is statically known to be of the right type.

It is therefore recommended to use split-xlist as follows when the type of the value is not known to be acceptable by split-xlist:

Examples:
> (define v : Any '(1 2 3))
> (match '(1 2 3)
    [(and (? (make-predicate (xlist Number¹ Number⃰)))
          (split-xlist (list (list a) (list b c) (? null?))
                       Number¹ Number⃰))
     'success])

- : Symbol [more precisely: 'success]

'success

2 Untyped versions of xlist

 (require xlist/untyped) package: xlist

syntax

xlist

Untyped version of xlist.

3 Special identifiers recognised by xlist

 (require xlist) package: xlist
 (require xlist/untyped)

syntax

^

This identifier can only be used within xlist forms.

syntax

once

This identifier can only be used within xlist forms.

syntax

This identifier is meant to be used within xlist forms, but is also equal to +inf.0 as a convenience. In the future, this package will make it possible for other packages to overload the meaning of the ^ and identifiers, so that the value of may depend on the packages loaded (for example a symbolic math package may want to attach a special value to .