Funcons-beta : Giving.cbs | PLAIN | PDF
Giving
\[\begin{align*} [ \ \KEY{Entity} \quad & \NAMEREF{given-value} \\ \KEY{Funcon} \quad & \NAMEREF{initialise-giving} \\ \KEY{Funcon} \quad & \NAMEREF{give} \\ \KEY{Funcon} \quad & \NAMEREF{given} \\ \KEY{Funcon} \quad & \NAMEREF{no-given} \\ \KEY{Funcon} \quad & \NAMEREF{left-to-right-map} \\ \KEY{Funcon} \quad & \NAMEREF{interleave-map} \\ \KEY{Funcon} \quad & \NAMEREF{left-to-right-repeat} \\ \KEY{Funcon} \quad & \NAMEREF{interleave-repeat} \\ \KEY{Funcon} \quad & \NAMEREF{left-to-right-filter} \\ \KEY{Funcon} \quad & \NAMEREF{interleave-filter} \\ \KEY{Funcon} \quad & \NAMEREF{fold-left} \\ \KEY{Funcon} \quad & \NAMEREF{fold-right} \ ] \end{align*}\] \[\begin{align*} \KEY{Meta-variables} \quad & \VAR{T}, \VAR{T}' <: \NAMEHYPER{../../../Values}{Value-Types}{values} \qquad \\& \VAR{T}\QUERY <: \NAMEHYPER{../../../Values}{Value-Types}{values}\QUERY \end{align*}\] \[\begin{align*} \KEY{Entity} \quad & \NAMEDECL{given-value}(\_ : \NAMEHYPER{../../../Values}{Value-Types}{values}\QUERY) \vdash \_ \TRANS \_ \end{align*}\]The given-value entity allows a computation to refer to a single previously-computed \(\SHADE{\VAR{V} : \NAMEHYPER{../../../Values}{Value-Types}{values}}\). The given value \(\SHADE{( \ )}\) represents the absence of a current given value.
\[\begin{align*} \KEY{Funcon} \quad & \NAMEDECL{initialise-giving}( \VAR{X} : ( \ ) \TO \VAR{T}') : ( \ ) \TO \VAR{T}' \\&\quad \leadsto \NAMEREF{no-given} ( \VAR{X} ) \end{align*}\]\(\SHADE{\NAMEREF{initialise-giving} ( \VAR{X} )}\) ensures that the entities used by the funcons for giving are properly initialised.
\[\begin{align*} \KEY{Funcon} \quad & \NAMEDECL{give}( \_ : \VAR{T}, \_ : \VAR{T} \TO \VAR{T}') : \TO \VAR{T}' \end{align*}\]\(\SHADE{\NAMEREF{give} ( \VAR{X}, \VAR{Y} )}\) executes \(\SHADE{\VAR{X}}\), possibly referring to the current \(\SHADE{\NAMEREF{given}}\) value, to compute a value \(\SHADE{\VAR{V}}\). It then executes \(\SHADE{\VAR{Y}}\) with \(\SHADE{\VAR{V}}\) as the \(\SHADE{\NAMEREF{given}}\) value, to compute the result.
\[\begin{align*} \KEY{Rule} \quad & \RULE{ & \NAMEREF{given-value} ( \VAR{V} ) \vdash \VAR{Y} \TRANS \VAR{Y}' }{ & \NAMEREF{given-value} ( \_\QUERY ) \vdash \NAMEREF{give} ( \VAR{V} : \VAR{T}, \VAR{Y} ) \TRANS \NAMEREF{give} ( \VAR{V}, \VAR{Y}' ) } \\ \KEY{Rule} \quad & \NAMEREF{give} ( \_ : \VAR{T}, \VAR{W} : \VAR{T}' ) \leadsto \VAR{W} \end{align*}\] \[\begin{align*} \KEY{Funcon} \quad & \NAMEDECL{given} : \VAR{T} \TO \VAR{T} \end{align*}\]\(\SHADE{\NAMEREF{given}}\) refers to the current given value.
\[\begin{align*} \KEY{Rule} \quad & \NAMEREF{given-value} ( \VAR{V} : \NAMEHYPER{../../../Values}{Value-Types}{values} ) \vdash \NAMEREF{given} \TRANS \VAR{V} \\ \KEY{Rule} \quad & \NAMEREF{given-value} ( \ ) \vdash \NAMEREF{given} \TRANS \NAMEHYPER{../../Abnormal}{Failing}{fail} \end{align*}\] \[\begin{align*} \KEY{Funcon} \quad & \NAMEDECL{no-given}( \_ : ( \ ) \TO \VAR{T}') : ( \ ) \TO \VAR{T}' \end{align*}\]\(\SHADE{\NAMEREF{no-given} ( \VAR{X} )}\) computes \(\SHADE{\VAR{X}}\) without references to the current given value.
\[\begin{align*} \KEY{Rule} \quad & \RULE{ & \NAMEREF{given-value} ( \ ) \vdash \VAR{X} \TRANS \VAR{X}' }{ & \NAMEREF{given-value} ( \_\QUERY ) \vdash \NAMEREF{no-given} ( \VAR{X} ) \TRANS \NAMEREF{no-given} ( \VAR{X}' ) } \\ \KEY{Rule} \quad & \NAMEREF{no-given} ( \VAR{U} : \VAR{T}' ) \leadsto \VAR{U} \end{align*}\]Mapping
Maps on collection values can be expressed directly, e.g., \(\SHADE{\NAMEHYPER{../../../Values/Composite}{Lists}{list} ( \NAMEREF{left-to-right-map} ( \VAR{F}, \NAMEHYPER{../../../Values/Composite}{Lists}{list-elements} ( \VAR{L} ) ) )}\).
\[\begin{align*} \KEY{Funcon} \quad & \NAMEDECL{left-to-right-map}( \_ : \VAR{T} \TO \VAR{T}', \_ : ( \VAR{T} )\STAR) : \TO ( \VAR{T}' )\STAR \end{align*}\]\(\SHADE{\NAMEREF{left-to-right-map} ( \VAR{F}, \VAR{V}\STAR )}\) computes \(\SHADE{\VAR{F}}\) for each value in \(\SHADE{\VAR{V}\STAR}\) from left to right, returning the sequence of resulting values.
\[\begin{align*} \KEY{Rule} \quad & \NAMEREF{left-to-right-map} ( \VAR{F}, \VAR{V} : \VAR{T}, \VAR{V}\STAR : ( \VAR{T} )\STAR ) \leadsto \\&\quad \NAMEHYPER{../.}{Flowing}{left-to-right} ( \NAMEREF{give} ( \VAR{V}, \VAR{F} ), \NAMEREF{left-to-right-map} ( \VAR{F}, \VAR{V}\STAR ) ) \\ \KEY{Rule} \quad & \NAMEREF{left-to-right-map} ( \_, ( \ ) ) \leadsto ( \ ) \end{align*}\] \[\begin{align*} \KEY{Funcon} \quad & \NAMEDECL{interleave-map}( \_ : \VAR{T} \TO \VAR{T}', \_ : ( \VAR{T} )\STAR) : \TO ( \VAR{T}' )\STAR \end{align*}\]\(\SHADE{\NAMEREF{interleave-map} ( \VAR{F}, \VAR{V}\STAR )}\) computes \(\SHADE{\VAR{F}}\) for each value in \(\SHADE{\VAR{V}\STAR}\) interleaved, returning the sequence of resulting values.
\[\begin{align*} \KEY{Rule} \quad & \NAMEREF{interleave-map} ( \VAR{F}, \VAR{V} : \VAR{T}, \VAR{V}\STAR : ( \VAR{T} )\STAR ) \leadsto \\&\quad \NAMEHYPER{../.}{Flowing}{interleave} ( \NAMEREF{give} ( \VAR{V}, \VAR{F} ), \NAMEREF{interleave-map} ( \VAR{F}, \VAR{V}\STAR ) ) \\ \KEY{Rule} \quad & \NAMEREF{interleave-map} ( \_, ( \ ) ) \leadsto ( \ ) \end{align*}\] \[\begin{align*} \KEY{Funcon} \quad & \NAMEDECL{left-to-right-repeat}( \_ : \NAMEHYPER{../../../Values/Primitive}{Integers}{integers} \TO \VAR{T}', \_ : \NAMEHYPER{../../../Values/Primitive}{Integers}{integers}, \_ : \NAMEHYPER{../../../Values/Primitive}{Integers}{integers}) : \TO ( \VAR{T}' )\STAR \end{align*}\]\(\SHADE{\NAMEREF{left-to-right-repeat} ( \VAR{F}, \VAR{M}, \VAR{N} )}\) computes \(\SHADE{\VAR{F}}\) for each value from \(\SHADE{\VAR{M}}\) to \(\SHADE{\VAR{N}}\) sequentially, returning the sequence of resulting values.
\[\begin{align*} \KEY{Rule} \quad & \RULE{ & \NAMEHYPER{../../../Values/Primitive}{Integers}{is-less-or-equal} ( \VAR{M}, \VAR{N} ) == \NAMEHYPER{../../../Values/Primitive}{Booleans}{true} }{ & \NAMEREF{left-to-right-repeat} ( \VAR{F}, \VAR{M} : \NAMEHYPER{../../../Values/Primitive}{Integers}{integers}, \VAR{N} : \NAMEHYPER{../../../Values/Primitive}{Integers}{integers} ) \leadsto \\&\quad \NAMEHYPER{../.}{Flowing}{left-to-right} ( \NAMEREF{give} ( \VAR{M}, \VAR{F} ), \NAMEREF{left-to-right-repeat} ( \VAR{F}, \NAMEHYPER{../../../Values/Primitive}{Integers}{int-add} ( \VAR{M}, 1 ), \VAR{N} ) ) } \\ \KEY{Rule} \quad & \RULE{ & \NAMEHYPER{../../../Values/Primitive}{Integers}{is-less-or-equal} ( \VAR{M}, \VAR{N} ) == \NAMEHYPER{../../../Values/Primitive}{Booleans}{false} }{ & \NAMEREF{left-to-right-repeat} ( \_, \VAR{M} : \NAMEHYPER{../../../Values/Primitive}{Integers}{integers}, \VAR{N} : \NAMEHYPER{../../../Values/Primitive}{Integers}{integers} ) \leadsto ( \ ) } \end{align*}\] \[\begin{align*} \KEY{Funcon} \quad & \NAMEDECL{interleave-repeat}( \_ : \NAMEHYPER{../../../Values/Primitive}{Integers}{integers} \TO \VAR{T}', \_ : \NAMEHYPER{../../../Values/Primitive}{Integers}{integers}, \_ : \NAMEHYPER{../../../Values/Primitive}{Integers}{integers}) : \TO ( \VAR{T}' )\STAR \end{align*}\]\(\SHADE{\NAMEREF{interleave-repeat} ( \VAR{F}, \VAR{M}, \VAR{N} )}\) computes \(\SHADE{\VAR{F}}\) for each value from \(\SHADE{\VAR{M}}\) to \(\SHADE{\VAR{N}}\) interleaved, returning the sequence of resulting values.
\[\begin{align*} \KEY{Rule} \quad & \RULE{ & \NAMEHYPER{../../../Values/Primitive}{Integers}{is-less-or-equal} ( \VAR{M}, \VAR{N} ) == \NAMEHYPER{../../../Values/Primitive}{Booleans}{true} }{ & \NAMEREF{interleave-repeat} ( \VAR{F}, \VAR{M} : \NAMEHYPER{../../../Values/Primitive}{Integers}{integers}, \VAR{N} : \NAMEHYPER{../../../Values/Primitive}{Integers}{integers} ) \leadsto \\&\quad \NAMEHYPER{../.}{Flowing}{interleave} ( \NAMEREF{give} ( \VAR{M}, \VAR{F} ), \NAMEREF{interleave-repeat} ( \VAR{F}, \NAMEHYPER{../../../Values/Primitive}{Integers}{int-add} ( \VAR{M}, 1 ), \VAR{N} ) ) } \\ \KEY{Rule} \quad & \RULE{ & \NAMEHYPER{../../../Values/Primitive}{Integers}{is-less-or-equal} ( \VAR{M}, \VAR{N} ) == \NAMEHYPER{../../../Values/Primitive}{Booleans}{false} }{ & \NAMEREF{interleave-repeat} ( \_, \VAR{M} : \NAMEHYPER{../../../Values/Primitive}{Integers}{integers}, \VAR{N} : \NAMEHYPER{../../../Values/Primitive}{Integers}{integers} ) \leadsto ( \ ) } \end{align*}\]Filtering
Filters on collections of values can be expressed directly, e.g., \(\SHADE{\NAMEHYPER{../../../Values/Composite}{Lists}{list} ( \NAMEREF{left-to-right-filter} ( \VAR{P}, \NAMEHYPER{../../../Values/Composite}{Lists}{list-elements} ( \VAR{L} ) ) )}\) to filter a list \(\SHADE{\VAR{L}}\).
\[\begin{align*} \KEY{Funcon} \quad & \NAMEDECL{left-to-right-filter}( \_ : \VAR{T} \TO \NAMEHYPER{../../../Values/Primitive}{Booleans}{booleans}, \_ : ( \VAR{T} )\STAR) : \TO ( \VAR{T} )\STAR \end{align*}\]\(\SHADE{\NAMEREF{left-to-right-filter} ( \VAR{P}, \VAR{V}\STAR )}\) computes \(\SHADE{\VAR{P}}\) for each value in \(\SHADE{\VAR{V}\STAR}\) from left to right, returning the sequence of argument values for which the result is \(\SHADE{\NAMEHYPER{../../../Values/Primitive}{Booleans}{true}}\).
\[\begin{align*} \KEY{Rule} \quad & \NAMEREF{left-to-right-filter} ( \VAR{P}, \VAR{V} : \VAR{T}, \VAR{V}\STAR : ( \VAR{T} )\STAR ) \leadsto \\&\quad \NAMEHYPER{../.}{Flowing}{left-to-right} ( \NAMEHYPER{../../../Values}{Value-Types}{when-true} ( \NAMEREF{give} ( \VAR{V}, \VAR{P} ), \VAR{V} ), \NAMEREF{left-to-right-filter} ( \VAR{P}, \VAR{V}\STAR ) ) \\ \KEY{Rule} \quad & \NAMEREF{left-to-right-filter} ( \_ ) \leadsto ( \ ) \end{align*}\] \[\begin{align*} \KEY{Funcon} \quad & \NAMEDECL{interleave-filter}( \_ : \VAR{T} \TO \NAMEHYPER{../../../Values/Primitive}{Booleans}{booleans}, \_ : ( \VAR{T} )\STAR) : \TO ( \VAR{T} )\STAR \end{align*}\]\(\SHADE{\NAMEREF{interleave-filter} ( \VAR{P}, \VAR{V}\STAR )}\) computes \(\SHADE{\VAR{P}}\) for each value in \(\SHADE{\VAR{V}\STAR}\) interleaved, returning the sequence of argument values for which the result is \(\SHADE{\NAMEHYPER{../../../Values/Primitive}{Booleans}{true}}\).
\[\begin{align*} \KEY{Rule} \quad & \NAMEREF{interleave-filter} ( \VAR{P}, \VAR{V} : \VAR{T}, \VAR{V}\STAR : ( \VAR{T} )\STAR ) \leadsto \\&\quad \NAMEHYPER{../.}{Flowing}{interleave} ( \NAMEHYPER{../../../Values}{Value-Types}{when-true} ( \NAMEREF{give} ( \VAR{V}, \VAR{P} ), \VAR{V} ), \NAMEREF{interleave-filter} ( \VAR{P}, \VAR{V}\STAR ) ) \\ \KEY{Rule} \quad & \NAMEREF{interleave-filter} ( \_ ) \leadsto ( \ ) \end{align*}\]Folding
\[\begin{align*} \KEY{Funcon} \quad & \NAMEDECL{fold-left}( \_ : \NAMEHYPER{../../../Values/Composite}{Tuples}{tuples} ( \VAR{T}, \VAR{T}' ) \TO \VAR{T}, \_ : \VAR{T}, \_ : ( \VAR{T}' )\STAR) : \TO \VAR{T} \end{align*}\]\(\SHADE{\NAMEREF{fold-left} ( \VAR{F}, \VAR{A}, \VAR{V}\STAR )}\) reduces a sequence \(\SHADE{\VAR{V}\STAR}\) to a single value by folding it from the left, using \(\SHADE{\VAR{A}}\) as the initial accumulator value, and iteratively updating the accumulator by giving \(\SHADE{\VAR{F}}\) the pair of the accumulator value and the first of the remaining arguments.
\[\begin{align*} \KEY{Rule} \quad & \NAMEREF{fold-left} ( \_, \VAR{A} : \VAR{T}, ( \ ) ) \leadsto \VAR{A} \\ \KEY{Rule} \quad & \NAMEREF{fold-left} ( \VAR{F}, \VAR{A} : \VAR{T}, \VAR{V} : \VAR{T}', \VAR{V}\STAR : ( \VAR{T}' )\STAR ) \leadsto \NAMEREF{fold-left} ( \VAR{F}, \NAMEREF{give} ( \NAMEHYPER{../../../Values/Composite}{Tuples}{tuple} ( \VAR{A}, \VAR{V} ), \VAR{F} ), \VAR{V}\STAR ) \end{align*}\] \[\begin{align*} \KEY{Funcon} \quad & \NAMEDECL{fold-right}( \_ : \NAMEHYPER{../../../Values/Composite}{Tuples}{tuples} ( \VAR{T}, \VAR{T}' ) \TO \VAR{T}', \_ : \VAR{T}', \_ : ( \VAR{T} )\STAR) : \TO \VAR{T}' \end{align*}\]\(\SHADE{\NAMEREF{fold-right} ( \VAR{F}, \VAR{A}, \VAR{V}\STAR )}\) reduces a sequence \(\SHADE{\VAR{V}\STAR}\) to a single value by folding it from the right, using \(\SHADE{\VAR{A}}\) as the initial accumulator value, and iteratively updating the accumulator by giving \(\SHADE{\VAR{F}}\) the pair of the the last of the remaining arguments and the accumulator value.
\[\begin{align*} \KEY{Rule} \quad & \NAMEREF{fold-right} ( \_, \VAR{A} : \VAR{T}', ( \ ) ) \leadsto \VAR{A} \\ \KEY{Rule} \quad & \NAMEREF{fold-right} ( \VAR{F}, \VAR{A} : \VAR{T}', \VAR{V}\STAR : ( \VAR{T} )\STAR, \VAR{V} : \VAR{T} ) \leadsto \NAMEREF{give} ( \NAMEHYPER{../../../Values/Composite}{Tuples}{tuple} ( \VAR{V}, \NAMEREF{fold-right} ( \VAR{F}, \VAR{A}, \VAR{V}\STAR ) ), \VAR{F} ) \end{align*}\]