rand00
Implement `Ring.map_rev_shortcircuit`
As is noted here (though wrongly called Ring.find_map_rev), this function would be useful for performance-reasons when updating the Ring ring-buffer defined in lib/conntest.ml.
The performance gain will probably be relatively small as the ring-buffer is not too big, but it's nice to avoid unneccesary iteration.
The idea is that Ring has a primarily functional interface, and the new map_rev_shortcircuit would allow one to modify the ringbuffer starting from the latest added element, and stop iterating when None is returned by the given lambda.
The type would then be:
val map_rev_shortcircuit : ('a -> 'a option) -> 'a t -> 'a t
@rand00 i am attempting to work on this issue but am stuck. on attempting to run dune build, i get the error File "lib/output.ml", line 696, characters 28-33: 696 | let sep_i = I.(string " | " <-> string " | ") in ^^^^^ Error: This expression has type string but an expression was expected of type attr help
Hey @waringa-mercy - thank you for working on this (:
You need to compile using the mirage tool - then the correct version of the libraries will be used. See https://github.com/rand00/conntest#compiling
When you want to iteratively compile when developing, then just run the last command: mirage build -f mirage/config.ml
@rand00 i am a bit late due to some personal issue but after informing outreachy, i was adviced to proceed and make contributions. I have been familiarizing myself as fast as possible. kindly bear with me if i ask very many questions
@rand00 the error has been resolved. thank you. From my limited understanding on information provided, map_rev_shortcircuit is supposed to be added into line 351. every line of code i try adding on there keeps giving me syntax error. so far this is what i have:
let map_rev_shortcircuit f r =
let len = Array.length r.ring in
let start = r.index in
let rec loop i =
if i = start || f r.ring.(i) = None then ()
else (
r.ring.(i) <- f r.ring.(i);
loop ((i + len - 1) mod len)
)
in
loop ((start + len - 1) mod len);
r
basicaly, it starts iterating the ring buffer from the latest added element, and stops iterating when the lambda function f returns None for an element. function first gets the length of the ring buffer starting index. The function checks two conditions: if i equals start or if applying the function f to the element at index i returns None. If either of these conditions is true, the function terminates.If both conditions are false, the function modifies the element in place with the new value and then calls the loop recursively .Then the loop function is called with the index of the element before the latest element in the ring buffer and f is applied to the ring buffer elements in reverse order starting from the latest element and stopping when f returns None.
@rand00 am still brainstorming a few ideas, i would appreciate your guidance whenever i am off
Good try! Though there are a couple of issues:
- the array from the input
Ring.tshould not be mutated, but a new array should be created - otherwise the user of the datastructure can observe the mutation - the lambda
fshould only be applied to the value in the ring if the value isSome v - you use some custom index calculations which are hard to maintain - it would be better if you use
wrap_reverse_iwhich has been tested. See its usage inget_previousandfold_left
@rand00 I have spent the entire weekend trying to solve this, hopefully i have.I defined function map_rev_shortcircuit that takes a function f and a Ring.t r as inputs and returns a new Ring.t as output. The function iterates over the elements of the input ring starting from the latest added element and applies the function f to each non-empty element of the ring until it returns None. If f returns None for an element, the iteration is stopped, and the function returns a new ring containing the modified elements up to that point. the function creates a copy of the input ring's array using avoid mutating the input ring. It then uses Ring.wrap_reverse_i to obtain the index of the element in the copy of the array that corresponds to the current iteration, and Ring.get_previous to obtain the previous element in the original ring. It then applies f to this element, and if f returns Some y, it updates the copy of the array with y at the corresponding index. If f returns None, the iteration is stopped by setting i to len.Finally, the function returns a new Ring.t with the updated array.