I am new to ocaml and a am trying to write a function that takes a list and returns list of pairs of first and last second and 2nd last and so forth .I have an idea of how to do this but only problem i have is that i dont know how to split the list in half.
What did you try to split your list in half? Note also that you need to make a decision for lists with an odd number of elements like
maybe convert to array first? then you index from both ends, etc. Or reverse the list, then recurse down both at the same time, stopping halfway (during reverse, compute length).
ETA: Either way, you have to allocate memory O(length of input) so you might as well just use the array-based method, I guess.
I found a function that splits a list in half on a inputed number.But i am looking for a shorter solution at divides list . length by 2 and on that element to split the list. For lists with odd number of elements it really doesnt matter.
Jeah i was thinking about rev but it would be much easier if i could split original list in half and rev the second part and then concat pairs of head and rec tails. It doesnt matter if list has odd number of elements because when one list runs out of elements the recursin will stop
Just have a function that takes the original list and a empty list. Build up the empty list(with the first half of the original list) until you reach the halfway point and then use the remainder of the original list and the built up empty list to generate your pairs.
Note: this assumes an even number of elements on the original list.
I’d suggest that a “list” in most ML languages, is a type that supports recursion, and recursion down the list-structure (from left-to-right) only. Other access-methods are implemented -via- that recursion. So any access-method that requires knowing the length, or indexing from the right end, intrinsically isn’t suitable for a list. But also, any method that builds a reversed list, has to know when to stop – this is equivalent to computing the length, which requires a full traverse. Furthermore, a reversed half-length list is going to take up more memory than a full-length array, and it isn’t at all obvious. that that array is slower to construct. All reasons to just construct the array, I think.
And Array.of_list is … so convenient for that.
ill try that thank you
I tried my very limited Ocaml skills on the reverse half-length list. Note only works on list with even number of elements.
let listPair lst = let len = List.length lst in let hLen = len/2 in let rec splitList lst empty depth = if depth = 0 then (lst, empty) else match lst with |  -> (, ) | hd::tl -> splitList tl (hd::empty) (depth - 1) in let rec pairs (l1, l2) = match (l1, l2) with | ((h1::t1), (h2::t2)) -> (h2, h1)::pairs (t1, t2) | _ ->  in pairs(splitList lst  hLen) let ans = listPair [1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19;20;] let () = List.iter ( fun (e1, e2) -> print_endline("<" ^ (string_of_int e1) ^ ", " ^ (string_of_int e2) ^ ">") ) ans
The above should give the more experienced Ocaml’ers something to critique.
I think it’s great that you’re trying to learn Ocaml, and this is an excellent solution for this problem! One suggestion:
Solving the problem for a list L, is the same as solving it for the reverse of that list, right? So you could
(a) reverse the list, in the process counting the length, N, and the reversed list RL
(b) then apply a version of “pairs” that takes a depth, to N, L, RL, and produces the first N pairs from L, RL.
© BTW, the “accumulating parameters” version of 'pairs" would produce those pairs in “inside-out order” (for [1;2;3;4] you’d get [2,3; 1,4]) so you might want to reverse the result.
[though, the version of pairs you write isn’t an “accumulating parameters” version, so no reverse is required there.]
Again, I think it’s great you’re doing this!
Yeah reversing the list would simplify the answer.
Below is a simple but inefficient solution. You could think about how to make it more efficient.
let rec take n xs = match n, xs with | 0, xs ->  | _,  ->  | n, x :: xs -> x :: take (n - 1) xs let rec zip xs ys = match xs, ys with | x :: xs, y :: ys -> (x, y) :: zip xs ys | , _ ->  | _,  ->  let split xs = let n = List.length xs in let ys = List.rev xs in zip xs ys |> take (n / 2) # split [1;2;3;4;5;6];; - : (int * int) list = [(1, 6); (2, 5); (3, 4)]
Using lists and list functionality?
My first attempt would get rid of the take function and check for depth in the zip function. My second attempt may look into combining the reverse and length function into one function which returns both length and reversed list.
let rec zip xs ys depth = if depth = 0 then  else ( match xs, ys with | x :: xs, y :: ys -> (x, y) :: zip xs ys (depth - 1) | _ ->  ) let split xs = let n = List.length xs in let ys = List.rev xs in zip xs ys (n / 2) let ans = split [1;2;3;4;5;6;] let () = List.iter (fun (e1, e2) -> print_endline("<" ^ string_of_int e1 ^ ", " ^ string_of_int e2 ^ ">") ) ans
You could re-write
take such that it returns both the first
n elements in a list and the remaining list. These two lists then can be zip’ed together. This becomes:
let split xs = let n = List.length xs in xs |> take (n/2) |> zip
With a slight change to
zip as well such that it takes its arguments in a pair:
let take : int -> 'a list -> 'a list * 'a list = fun n xs -> ... let zip : 'a list * 'b list -> ('a * 'b) list = fun (xs, ys) -> ...
OK! I see. Walk through the list building up a list of the first elements until you reach the halfway point and then return the built up list and the tail.
Are we on the same page?
let take depth lst = let rec takeAux lst empty depth = if depth = 0 then (lst, empty) else ( match lst with | hd::tl -> takeAux tl (hd::empty) (depth - 1) | _ -> (lst, empty) ) in takeAux lst  depth let rec zip (l1, l2) = match (l1, l2) with | h1::t1, h2::t2 -> (h2, h1)::zip (t1, t2) | _ ->  let lst = [1;2;3;4;5;6;] let () = let n = List.length lst in lst |> take (n/2) |> zip |> List.iter (fun (e1, e2) -> print_endline("<" ^ string_of_int e1 ^ ", " ^ string_of_int e2 ^ ">"))
emptyis not empty
- you can use pattern matching instead of if-then-else and keep the code flat:
let take : int -> 'a list -> 'a list * 'a list = fun n xs -> let rec loop acc n xs = match n, xs with | 0, xs -> (acc, xs) | _,  -> (acc, ) | n, x::xs -> loop (x::acc) (n-1) xs in loop  n xs
Looking at my own code, I could use better names:
tail for the two lists that are returned.
Thanks for the pointers and tips.