let rec remove_last (l: 'a list) : 'a list = match l with
| [] -> []
| [_] -> []
| hd::tl -> hd :: (remove_last tl)
let arrange (s: 'a list): 'a list =
let rec arr2 (lst: 'a list) (inc: int) (lengthList: int) : 'a list = match lst with
| [] -> []
| ed :: lst -> if lst <> [] then
if inc mod 2 = 0 then
ed :: (List.nth lst (lengthList - 1)) :: arr2(remove_last lst) (inc+1) (lengthList - 2)
else
(List.nth lst (lengthList - 1)) :: ed :: arr2(remove_last lst) (inc+1) (lengthList - 2)
else
ed :: []
in arr2 s 0 (List.length s - 1)
The results are not terrible, I fail when it comes to big list size because it takes too much time :
One easy way to reverse the array is to have a pair of array, one is the reversed version. Then from a (a,b) pair, if we recurse with the (b,a), it will be like a reversion of the array at no cost.
Without array, one can get the list length, the reversed list, compose a pair of both lists (original and reversed). Suppressing the first of both is O(1)ā¦ and decreasing a counter set initially to length/2 is also O(1).
Reading on my phone, it looks like you can simplify.
Since it is asked that you donāt mutate the input, I would stick to applying functions recursively to the initial list. I think you only need 2 functions.
Also, I would try not to call `List.nthā at all.
I guess it would not be fair that we solve the puzzle for you, but the strong hints are: do not use List.length nor List.nth. But you can use List.revā¦
Hello all,
Thanks for replying to this topic.
I wanted to get some advices, sorry for my poorly formuled question.
I will reply for each person what I tried :
@sanette I only use once List.length and I always do a -2 or -1 operation on an int.
I only manipulate integers, so It should be better than one of my old versions calling a lot List.length at each call of the function.
For List.rev, I used it and associated it with this :
List.hd (List.rev lst)
But I know that List.rev is same complexity O(n) than List nth because I have to go through all the list to get the last element, or reverse all the list to get the first element.
I tested some things about this solution : the performance is nearly the same on this website (0.03 ms difference when I did my tests, not sure if it is really impactful).
@benjamin-thomas Yes I try to do with this type of idea at the beginning.
But at one moment I have to call the nth function to get the last elementā¦
Is it really costing a lot when I define a function into multiple little functions ?
Maybe there is some magic behind it and I donāt see itā¦
@Frederic_Loyer and @vrotaru Thank you for the suggestion about the array.
I wasnāt aware about this type because it only specifies 'a list in the exercise.
I will try to change my solution and do it with yours with the array type.
Update,
I solved it with arrays and doing some tricks with the modulo.
It is quite dirty unfortunately even if I understood all the cases.
edit : I deleted solution answer (not sure about the codewars thing about posting solution), it would be better for a solution logic after some thoughts :
logic
I convert it in array first.
I define i incrementator.
I go through the array and get the i index and the arrayLength - i index values.
If my i is even, it is (a,b)
If my i is odd, it is (b,a)
I return my list, all with recursive.
The array solution is very good thanks for giving this hint.
I saw some people with the Array solution.
The idea I have proposed is to use List.rev once, List.length once (O(n)), and call an auxiliary function with the_list, the_list_reversed, thelength/2. The auxiliary will call itself recursively, but only use O(1) operations (removing a item, composing the result, swapping lists. The end condition will be on the counter since at the end, each list contains half of the original list.
Sorry, I misunderstood it.
I got the part that I only need to check List.length/2.
I didnāt use at all the reverse function because it doesnāt need to be reversed.
When you increment a given said i variable, you can verify if i is even or odd and do this (a,b) or (b,a) when i is odd or even.
So I went with the solution of not doing it at all finally and changing a lot with converting it to an array and changing the logic of the program.
I should try your solution too because it seems interesting.
Finally, call the aux with Length of the list, and decrement it by two at each step. There are two final conditions : the counter= 0 and the_counter=1.
let arrange =
let rec aux acc = function
| [] -> List.rev acc
| x :: y :: xs -> aux (y :: x :: acc) (List.rev xs)
| [ x ] -> aux (x :: acc) []
in
function
| [] -> []
| x :: xs -> x :: aux [] (List.rev xs)
;;
Unfortunately, it doesnāt pass the āBig sizeā test.
Since accessing the last element of a list is the most expensive thing we could do, and given the fact that we have to do this multiple times, Iām not even sure we can pass the exercise without going through an array.
Since you asked for advice, I thought I should mention that I found the list exercises on OCamlās website really good: Exercises
Working through them really helped me understand the bigger picture.
I have a solution that passed the āBig sizeā test with pure lists. Itās not exactly straightforward (and I found the description of the exercise misleading too) but itās possible.
It uses more or less the algorithm that @Frederic_Loyer described above, manipulating two lists at the same time (normal and reversed) and swapping them after each step.
let arrange (s: 'a list): 'a list =
let rec aux l lr n =
match n with
| 0 -> []
| 1 -> [List.hd l]
| _ -> (List.hd l) :: (List.hd lr) ::
aux (List.tl lr) (List.tl l) (n-2)
in
aux s (List.rev s) (List.length s)
The point is to place List.rev outside the recursive aux function. The complexity is O(n).
my version was essentially the same but with pattern matching (for the list):
let rec loop l t s rev =
if l = 0 then t
else if l = 1 then (List.hd s) :: t
else match s, rev with
| x1 :: rest1, x2 :: rest2 ->
loop (l-2) (x2 :: (x1 :: t)) rest2 rest1
| _ -> failwith "Should not happen"
let arrange s =
List.rev (loop (List.length s) [] s (List.rev s))
In a small benchmark, this does not seem to make a difference, except for very large n, where pattern matching seems faster. Anybody knows why? Maybe itās just because of tail recursivity
Your program deconstruct the each list once (matchā¦). My program deconstruct the lists twi (hd, tl). It can make a difference.
The idea to construct the result with an accumulator seems good. It makes the function tail recursive and avoids many āreturnā in the assembly generated program. However I could have written
let[@tail_mod_cons] rec aux l lr n =
(With OCaml >=4.14)
And let the compiler optimise the function in a way similar to tail recursive function. See:
On my prior (second) attempt, I had used only one partial function, once (List.tl).
I then wondered if it would be possible at all to use only total functions and I think the result is okay (a bit more complicated but still okay).
Iāve been wondering for a while what it means to express a function using partial functions vs only using total functions. I understand it may not matter in practice, but Iām wondering if it has meaning āmathematicallyā so to speak.
Iād be happy to read anyoneās thoughts on this matter.
let arrange lst =
let rec aux flip n acc fwd bwd =
match (fwd, bwd) with
| (x :: xs, y :: ys) ->
if n = 0 then
acc
else if n = 1 then
x :: acc
else
let new_acc =
if flip then
x :: y :: acc
else
y :: x :: acc
in
aux (not flip) (n - 2) new_acc xs ys
| _ -> []
in
List.rev @@ aux false (List.length lst) [] lst (List.rev lst)
;;
@sanette
I have tried my program: 1.455s
Itās [@tail_mod_cons] version: 1.364s
Itās [@tail_mod_cons] version with pattern matching: 0.801s
And curiously, your version: 1.381s
These times are from a ocamlopt compiled version, looping 100 times arrange(r) where r is a list of 100 000 items.
Then having a tail recursion is niceā¦ but if we have de reverse the list, the gain of the optimisation is lost. And [@tail_mod_cons] indicates a slight gain (without changing the logic). The pattern matching however has an important impact. With List.hd and List.tl, Ocaml has to check twice if the list is not nul. With a pattern matching, only once.
