/** * This module contains strategies for working on lists using indexes. * An indexed list works similarly to an array in that every element of * the list is associated with in an integer index, and the first * element has index 1. * * Adding the indices to a list is done by add-indices. * */ module collection/list/index imports collection/list/cons strategy/traversal/simple strategies /** * Get the n-th element of a list. * The first element has index 1. * * @type (Int, List(a)) -> a * @inc test-index */ index = ?(i, <id>); index(|i) strategies /** * Get the i-th element of a list. * The first element has index 1. * * @type List(a) -> a */ index(|i) = at-index(?t | <dec> i); !t strategies /** * Get index of element in list. * * @type (a, List(a)) -> Int */ get-index = Gind0 ; rec x(Gind1 <+ Gind2 ; x) /** @internal */ Gind0 : (x, ys) -> (1, x, ys) /** @internal */ Gind1 : (n, x, [x | xs]) -> n /** @internal */ Gind2 : (n, y, [x | xs]) -> (<add> (n, 1), y, xs) get-index0(s) = at-suffix([s | id]; ![]); length strategies /** * Change element in list. * The first element has index 0. * * @type (Int, a, List(a)) -> List(a) * @inc test-set-index */ set-index = ?(i, x, xs) ; <at-index(!x)> (i, xs) /** * Apply s at the specified index * The first element has index 0. * * @type (Int, List(a)) -> List(a) */ at-index(s) = ?(i, <id>) ; at-index(s | i) /** * Apply s at the specified index i. * The first element has index 0. * * @type List(a)) -> List(a) */ at-index(s | i) = let next(|j) = if !j => i then [s | id] else [id | next(|<inc> j)] end in next(|0) end /** * Apply s to the list containing the elements * from index i onwards from the original list. * The first element has index 0. * * @type List(a) -> List(a) */ at-index-tail(s|i) = let next(|j) = if !j => i then s else [id | next(|<inc> j)] end in next(|0) end strategies /** * Insert element in list. * * @type (Int, a, List(a)) -> List(a) * @inc test-insert */ insert = Ins0; rec x(Ins1 <+ Ins2(x)) /** @internal */ Ins0: (i, x, ys) -> (0, i, x, ys) /** @internal */ Ins1: (i, i, x, xs) -> [x | xs] /** @internal */ Ins2(r): (n, i, x, [y | ys]) -> [y | <r>(<add> (n, 1), i, x, ys)] strategies /** * Map a strategy over a list where the strategy takes the index as a term argument. * * @param Strategy to apply to all the elements of the list. * @param The first index (e.g. 0 or 1) * @type List(a) -> List(b) */ nmap(s : Int * a -> b | i) = [] + [s(|i) | nmap(s | <inc> i)] /** * Apply strategies that require some knowledge of the index of an element * to the elements of the list. * * The index of the first element is 1. * * @param Int * a -> b * @type List(a) -> List(b) * @inc test4a * @inc test4b */ map-with-index(s) = let apply(|i) = <s> (i, <id>) in nmap(apply | 1) end /** * Adds indices to the elements of a list. * The index of the first element is 1. * * Example: <add-indices> [1,2,3] => [(1,1),(2,2),(3,3)] * * @type List(a) -> List((Int, a)) * @inc test5 */ add-indices = map-with-index(id)