Effect-free loops as folds #
Id.run do code elaborates its for loops to forIn over the iterated container, with the
mutable variables as the loop state. This module relates such loops to folds over lists, so that
imperative code can be compared with a functional specification by rewriting.
- A legacy range
[a:b]iterates overList.range' a (b - a), and[0:n]overList.range n(Std.Legacy.Range.forIn_eq_forIn_range'_sub,Std.Legacy.Range.forIn_eq_forIn_range, and theirforIn'twins). Core states the general case withStd.Legacy.Range.size. - A body that only yields is a left fold:
List.forIn_eq_pure_foldlandList.idRun_forIn_eq_foldltake the yield equation as a hypothesis on the elements of the list, so the body may use facts about the index.Std.Internal.forIn_eq_pure_foldl_toListextends them to every container with aStd.Internal.PureForIninstance (arrays, ranges, slices,Option,Vector, …). Core'sList.forIn_pure_yield_eq_foldlcovers the bodies that are syntacticallypure (.yield _). - Two loops agree when their bodies agree on the iterated elements (
List.forIn_congr,Std.Internal.forIn_congr_toList,Std.Legacy.Range.forIn_congr). - A loop over
xs ++ ysrunsysfrom wherexsstopped (List.forIn_append), and from the statexsreturns whenxsnever stops early (List.forIn_append_of_yield). - A fold through a prescribed sequence of states ends in the last state
(
List.foldl_eq_of_trace,List.foldl_range'_eq_of_trace). - A fold over a pair state whose components do not read each other splits into two folds
(
List.fst_foldl,List.snd_foldl); the side condition holds bysimpfor the tuples thatdothreads through a loop with several mutable variables. - The verification conditions of a loop over a range decompose
List.range' s n stepaspref ++ cur :: suff;List.eq_add_mul_length_of_range'_eq_append_consandList.length_lt_of_range'_eq_append_consrecover the index.
The loop_norm simp set collects these rewrites with core's and the monad laws that expose a
yield-only body; simp only [loop_norm] turns most Id.run do loops with yield-only bodies into
List.foldl.
Legacy ranges as lists #
A for loop over [a:b] is the loop over List.range' a (b - a).
A for loop over [0:n] is the loop over List.range n.
The forIn' twin of forIn_eq_forIn_range'_sub.
The forIn' twin of forIn_eq_forIn_range.
Bodies that only yield #
A loop whose body yields g b a on every element a of the list is the left fold of g.
The forIn' twin of forIn_eq_pure_foldl, for a body that does not use the membership proof
in its result.
forIn'_eq_pure_foldl read through Id.run.
Congruence #
Concatenation #
A loop over xs ++ ys runs the loop over xs, as the fold of List.forIn_eq_foldlM, and
continues over ys unless that fold stopped.
When the body only yields on xs, a loop over xs ++ ys is the loop over ys started from
the state the loop over xs returns.
Folds through a sequence of states #
The first component of a left fold over pairs, when the first component of each step does not depend on the second component of the state, is the fold of the first components.
The second component of a left fold over pairs, when the second component of each step does not depend on the first component of the state, is the fold of the second components.
The element at position pref.length of List.range' s n step is s + step * pref.length,
as the verification conditions of a loop over a range need.
A loop over [a:b] whose body yields g acc i at every index a ≤ i < b is the left fold
of g over List.range' a (b - a).
forIn_eq_pure_foldl read through Id.run.
Containers iterating over a list #
List.forIn_eq_pure_foldl for every container whose loop is the loop over
ForIn.toList.
forIn_eq_pure_foldl_toList read through Id.run.
The forIn' twin of forIn_eq_pure_foldl_toList, for a body that does not use the
membership proof in its result.
Two loops over a container that iterates over ForIn.toList agree when their bodies agree on
its elements.
Normalization #
The dependent twin of ite_pure_yield.