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 ['b','o','b'].
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!
1 Like
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.
First attempt.
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) -> ...
1 Like
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 ^ ">"))
1 Like
Minor points:
-
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: head and tail for the two lists that are returned.
Thanks for the pointers and tips.
1 Like