Return list of items from list in OCaml

Question

I am new to OCaml, and now I am trying to implement a function that returns a list of elements of a given list x in indices in list y .

For example, this function should perform the following calculation: [5,6,7,8], [0, 3] => [5, 8]

I am not sure how to store temporary variables in ML and have no clear idea of ​​how this works. However, I know how to find an item from a list with a specified index.

Any idea would be appreciated, but I would like to use recursive functions and avoid the List module.

Answer 1

No need for temporary variables, just use recursion!

 # let rec indices xs = function | i :: is -> (List.nth xs i) :: indices xs is | [] -> [] ;; val indices : 'a list -> int list -> 'a list = <fun> # indices [5;6;7;8] [0;3] ;; - int list = [5; 8] 

It creates a list by looking at each provided pointer, and then takes it to the list returned by the next step.

Hope this is also optimized to tail recursive form, but I'm not sure about that. You might want to change it to the correct tail recursiveness, but I will leave it to you.

Answer 2

I was seduced and implemented the lightning solution that I proposed @ftk.

 (* A 'zipper' on the data structure "foo" is a derived data structure that represents a position in the data structure "foo", that can be filled with an element. You can think of this as a "cursor" on some element in the structure, that can moved in various directions to point to other elements of the structure. If the structure "foo" does not have random access, keeping a zipper allows to access the pointed element quickly (instead of having to look at it from the top of the structure again each time); its neighbors can be acccessed as well by moving the zipper. A cursor on a list has this form: cursor v [a; b; c; d; e; f] It can be represented as a value of type 'a list * 'a * 'a list where the first list denotes the element before the cursor, and the second the elements after it. To be able to access the left neighbor of the cursor in constant time, we store the left elements in reverse order (rightmost first), so the zipper actually is ([b; a], c, [d; e; f]) Zippers can be adapted to lot of data structures, including in particular trees. There are neat ways to define them as the "derivative" (in a calculus-like sense) of datatypes. See http://en.wikipedia.org/wiki/Zipper_(data_structure) for more information. *) let move_right = function | (left, x, x' :: right) -> (x :: left, x', right) | (_, _, []) -> raise Not_found let move_left = function | (x' :: left, x, right) -> (left, x', x :: right) | ([], _, _) -> raise Not_found let elem (left, e, right) = e (* zipper of a list *) let zipper = function | [] -> raise Not_found | x :: xs -> ([], x, xs) let rec iterate fx = function | 0 -> x | n -> iterate f (fx) (n - 1) let get_all data indices = let get_next index (pos, zip, acc) = let zip' = let move = if index < pos then move_left else move_right in try iterate move zip (abs (index - pos)) with Not_found -> invalid_arg ("invalid index " ^ string_of_int index) in (index, zip', elem zip' :: acc) in let (_pos, _zip, result) = List.fold_right get_next indices (0, zipper data, []) in result 

Usage example:

 # get_all [0;2;4;6;8;10] [2;0;1;4];; - : int list = [4; 0; 2; 8] # get_all [0;2;4;6;8;10] [2;0;1;6;4];; Exception: Invalid_argument "invalid index 6". 

If the list from which you can get items is large, it can be noticeably faster than List.map (List.nth data) :

 let slow_get_all data indices = List.map (List.nth data) indices let init n = Array.to_list (Array.init n (fun i -> i)) let data = init 100_000 let indices = List.map (( * ) 100) (init 1000) (* some seconds *) let _ = slow_get_all data indices (* immediate *) let _ = get_all data indices 

Of course, this is all an exercise, because in practice, if performance is important, you will transform data into data structures that are more efficient for random access, such as arrays.

Answer 3

mange answer illustrates well the power of functional programming. Let me reiterate the point: there is no need for temporary variables, just use recursion.

If you want to get rid of the last call to the List library, you can:

• Use the mange indices function and List.nth function. This is not a lot of fun, and you may prefer to avoid systematically re-scanning your list x for each element of your list y .

• Use the recursive function to scan lists x and y at the same time. For example, you can:

  • put the elements of list x as many times as the value of the first element of list y .
  • in the remaining list x , reserve the first element, place the head y and continue with the remainders x and y .

I will leave the details of how the devils dwell, as usual, before you.

Answer 4

You need a function from two lists; the second list shows the indices for the first list. There are two possibilities: the second list is sorted in ascending order, or the second list is not sorted in any way. If the second list is sorted, your function will be much more efficient. This is due to the fact that the list can be effectively moved from left to right, but random access to an element with a given index is not fast.

In any case, a tail recursive solution is possible. (I have a suspicion that this is a matter of homework ...)

The idea is not to use any temporary variables, but to build the result when viewing lists. Think about your problem in terms of mathematical induction. What is the basis of induction? An empty index list gives an empty result. What is the induction step? Take the next given index from the second list, adding one element from the first list to the result and assume (by induction) that all other indexes will be processed correctly.

Here's what you can do if the second list is sorted in ascending order, without duplicate items. indices_tr is a tail recursive function with four arguments; result is the previously accumulated result list, xs is the remainder of the first list, n is the current index in this list, and is is the rest of the index list.

 let indices xs is = let rec indices_tr result (x::xs) n = function | [] -> result | i::is when i==n -> indices_tr (x::result) xs (n+1) is | is -> indices_tr result xs (n+1) is in indices_tr [] xs 0 is ;; 

Warning that an empty list is not being processed.

The result is a list in reverse order:

  # indices [1;3;5;7] [0;1;2];; - : int list = [5; 3; 1] 

You cannot do better with a clean tail recursive solution; you can of course apply List.rev to this.