CODEWITHSUNDEEP
ocamlfoldleft
MAMR
MAMR

Reputation: 1

ocaml fold_left all elements with even index on left and elements with uneven index on right

I have a problem with the following assignment:

The function fold_left can be used to implement many operations that scan through a list from left to right. It takes three arguments: a function f, an initial accumulator, and a list. For each element x in the list, the currect accumulator is combined with x to produce the next accumulator value; the result of fold_left is the final accumulator value. Consult the lecture slides or the documentation for the precise definition!

the task is the follwoing: we have to implement the function f acc v so that it will have all elements with an even index on the left side and all elements with an uneven index on the right side. with the element with the index 0 being in the middle: something like this: [an; ...; a0; an-1]

i have the following function which does not pass hidden tests..but i sadly have no idea what my method does not cover:

let f acc v = 
  if List.length acc = 0 then 
    acc @[v] 
  else if List.length acc mod 2 = 0 then 
    v :: acc 
  else List.length acc mod 2 = 0 then 
    acc @ [v]

Upvotes: 0

Views: 165

Answers (1)

Chris
Chris

Reputation: 36536

As you go through a fold, your accumulator is the only state you have. It's the only way your function has any clue about what's going on. Choosing the type of that accumulator is key.

So, what do you need to know as you go through your fold?

  • The index of the element, starting at 0.
  • The element at index 0.
  • The elements at even indices.
  • The elements at odd indices.

But Chris! You can only pass one accumulator value, and that's four values! Can't you count?

No one said the one value couldn't be a tuple or a list containing multiple values.

Consider the following, which separates out even and odd indexed elements. Some elements of this sample replaced with ... to prevent just completely providing a copy and paste solution.

# List.fold_left 
    (fun (i, evens, odds) x -> 
       if i mod 2 = 0 then (i+1, ..., ...) 
       else (i+1, ..., ...)) 
    (0, [], []) 
    [1; 2; 3; 4; 5; 6];;
- : int * int list * int list = (6, [5; 3; 1], [6; 4; 2])

Your proposed solution using the length of the accumulator and either consing or appending could work, but as noted in comments, you have a syntax error. Your final comparison is unnecessary. You know that List.length acc is not 0 and not evenly divisible by 2. There is only one remaining state it could be in.

# let f acc v =
    if List.length acc = 0 then
      acc @ [v]
    else if List.length acc mod 2 = 0 then
      v :: acc
    else
      acc @ [v];;
val f : 'a list -> 'a -> 'a list = <fun>
# List.fold_left f [] [1;2;3;4;5;6];;
- : int list = [5; 3; 1; 2; 4; 6]

The inefficiency comes from how lists work in OCaml. They're singly linked. The only way to calculate the length or to append to the end of a list is to walk the entire list. You do that (potentially multiple times) on each iteration of your fold. The fold is O(n) so doing an O(n) operation on each iteration means the whole thing is O(n^2). For a list with a few elements? No big deal. Now imagine one of the test cases has 10,000 elements. Suddenly you have a problem, because 10,000 squared is 100,000,000. Even if I have to do an O(n) operation several times on a 10,000 element list, it'll never take nearly as long.

Now imagine 10,000,000 elements in the list. Squaring that is 100,000,000,000,000. It might look like your computer is simply frozen.

Upvotes: 3

Related Questions