Split a list into two equal lists in F #

Question

I am really new to F # and I need help with the F # problem.

I need to implement a cut function that splits the list in half so that the output is ...

cut [1; 2; 3; 4; 5; 6] ;;

val it: int list * int list = ([1; 2; 3], [4; 5; 6])

I can assume that the list length is even.

I also need to define a helper function gencut (n, xs) that cuts xs into two parts, where n sets the size of the first part:

gencut (2, [1; 3; 4; 2; 7; 0; 9]) ;;

val it: int list * int list = ([1; 3], [4; 2; 7; 0; 9])

Normally, I would not ask for the use of exercises, but I really do not understand where to start. Any help, even if it is just a push in the right direction, will help.

Thanks!

Answer 1

Since your list has an even length and you cut it in half in half, I recommend the following (psuedocode first):

• Start with two pointers: slow and fast .
• slow goes through the list one item at a time, fast executes two items at a time.
• slow adds each item to the battery variable, and fast moves forward.
• When the fast pointer reaches the end of the list, the slow pointer will only have half the number of elements in the middle, so it is in the middle of the array.
• Return the slow elements by stepping over + the remaining elements. It should be two lists, neatly arranged in half.

The above process requires one crawl on the list and runs in O (n) time.

Since this is homework, I won’t give a complete answer, but just for you to start partially, here is what you need to cut the list in half:

 let cut l = let rec cut = function | xs, ([] | [_]) -> xs | [], _ -> [] | x::xs, y::y'::ys -> cut (xs, ys) cut (l, l) 

Note x::xs steps 1 element, y::y'::ys steps two.

This function returns the second half of the list. It is very easy to change it so that it also returns the first half of the list.

Answer 2

You are looking for a list in F #. There was a big answer from @Juliet in this SO topic: Slicing as functionality from a list in F #

It basically comes down to the fact that it is not built in, since F # lists do not have a constant time index, but you can get around this as a detailed one. Her approach, applied to your problem, will give a (not so effective but effective) solution:

 let gencut(n, list) = let firstList = list |> Seq.take n |> Seq.toList let secondList = list |> Seq.skip n |> Seq.toList (firstList, secondList) 

Answer 3

(I did not like my previous answer, so I deleted it)

The first thing to start when attacking list problems is to look at the list module, which is filled with higher-order functions that summarize many common problems and can give you concise solutions. If you cannot find something suitable there, you can look at the Seq module for solutions like @BrokenGlass (but you may run into performance problems there). Then you will want to consider recursion and pattern matching. There are two types of recursion that you will have to consider when processing lists: tail and non-tail. There are trade-offs. Tail solutions recursively involve using a drive to pass state around, allowing you to place a recursive call at the tail position and avoid large lists. But then you usually get an inverted list! For example,

Solving the tail gencut solution:

 let gencutTailRecursive n input = let rec gencut cur acc = function | hd::tl when cur < n -> gencut (cur+1) (hd::acc) tl | rest -> (List.rev acc), rest //need to reverse accumulator! gencut 0 [] input 

gencut non-tail recursive solution:

 let gencutNonTailRecursive n input = let rec gencut cur = function | hd::tl when cur < n -> let x, y = gencut (cur+1) tl //stackoverflow with big lists! hd::x, y | rest -> [], rest gencut 0 input 

Once you have the gencut solution, it is very easy to define cut :

 let cut input = gencut ((List.length input)/2) input 

Answer 4

Here's another way to do this using the built-in library functions, which may or may not be clearer than some other answers. This solution also requires only an input traversal. My first thought after I looked at your problem was that you want something like List.partition lines, which splits the list into two lists based on a given predicate. However, in your case, this predicate will be based on the index of the current element, which cannot be processed by the section, despite the index for each element.

We can create our own equivalent of this behavior using fold or foldBack. I will use foldBack here, as this means you don’t have to change lists after that (see Stevens' excellent answer). What we're going to do here is to use the fold to provide our own index along with two output lists, all as a drive. Here is a generic function that will split your list into two lists based on index n:

 let gencut n input = //calculate the length of the list first so we can work out the index let inputLength = input |> List.length let results = List.foldBack( fun elem acc-> let a,b,index = acc //decompose accumulator if (inputLength - index) <= n then (elem::a,b,index+1) else (a,elem::b,index+1) ) input ([],[],0) let a,b,c = results (a,b) //dump the index, leaving the two lists as output. 

So, you see that we are running foldBack with the initial battery value ([], [], 0). However, since we start at the end of the list, 0, representing the current index, must be subtracted from the total length of the list to get the actual index of the current item.

Then we just check to see if the current index falls in the range n. If so, we update the drive by adding the current item for list a, leave list b alone and increase the index by 1: (elem :: a, b, index + 1). In all other cases, we do the same, but instead add an element to the list b: (a, elem :: b, index + 1).

Now you can easily create your own function, which splits the list in half, creating another function over this:

 let cut input = let half = (input |> List.length) / 2 input |> gencut half 

I hope this can help you!

 > cut data;; val it : int list * int list = ([1; 2; 3], [4; 5; 6]) > gencut 5 data;; val it : int list * int list = ([1; 2; 3; 4; 5], [6]) 

EDIT: you can avoid index negation by specifying the length as the initial value of the accumulator and negating it on every cycle, rather than increasing it - perhaps easier:

 let gencut n input = let results = List.foldBack( fun elem acc-> let a,b,index = acc //decompose accumulator if index <= n then (elem::a,b,index-1) else (a,elem::b,index-1) ) input ([],[],List.length input) let a,b,c = results (a,b) //dump the index, leaving the two lists as output. 

Answer 5

I have one homework, it was my decision. I'm just a student and new to F #

 let rec gencut(n, listb) = let rec cut n (lista : int list) (listb : int list) = match (n , listb ) with | 0, _ -> lista, listb | _, [] -> lista, listb | _, b :: listb -> cut (n - 1) (List.rev (b :: lista )) listb cut n [] listb let cut xs = gencut((List.length xs) / 2, xs) 

This is probably not the best recursive solution, but it works. I think,

Answer 6

You can use List.nth for random access and for understanding lists to create a helper function:

 let Sublist xy data = [ for z in x..(y - 1) -> List.nth data z ] 

This will return the [x..y] elements from the data. Using this, you can easily generate gencut and cut functions (don't forget to check borders on x and y) :)

Answer 7

check this:

 let gencut s xs = ([for i in 0 .. s - 1 -> List.nth xs i], [for i in s .. (List.length xs) - 1 -> List.nth xs i]) 

you just call

 let cut xs = gencut ((List.length xs) / 2) xs 

with n of duration n, only one iteration is divided into two