Split list into two equal lists in F?

Since your list has an even length, and you're cutting it cleanly in half, I recommend the following (psuedocode first): Start with two pointers: slow and fast slow steps through the list one element at a time fast steps two elements at a time slow adds each element to an accumulator variable, while fast moves foward When the fast pointer reaches the end of the list, the slow pointer will have only stepped half the number of elements, so its in the middle of the array Return the elements slow stepped over + the elements remaining. This should be two lists cut neatly in half The process above requires one traversal over the list and runs in O(n) time Since this is homework, I won't give a complete answer, but just to get you partway started, here's what it takes to cut the list cleanly 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 modify it so it returns the first half of the list as well.

Since your list has an even length, and you're cutting it cleanly in half, I recommend the following (psuedocode first): Start with two pointers: slow and fast. Slow steps through the list one element at a time, fast steps two elements at a time. Slow adds each element to an accumulator variable, while fast moves foward.

When the fast pointer reaches the end of the list, the slow pointer will have only stepped half the number of elements, so its in the middle of the array. Return the elements slow stepped over + the elements remaining. This should be two lists cut neatly in half.

The process above requires one traversal over the list and runs in O(n) time. Since this is homework, I won't give a complete answer, but just to get you partway started, here's what it takes to cut the list cleanly 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 modify it so it returns the first half of the list as well.

1 @Juliet - that's really neat! – Stephen Swensen Feb 1 at 22:21 I really appreciate the help! Thanks!

– user598907 Feb 2 at 22:58.

You are looking for list slicing in F#. There was a great answer by @Juliet in this SO Thread: Slice like functionality from a List in F# Basically it comes down to - this is not built in since there is no constant time index access in F# lists, but you can work around this as detailed. Her approach applied to your problem would yield a (not so efficient but working) solution: let gencut(n, list) = let firstList = list |> Seq.

Take n |> Seq. ToList let secondList = list |> Seq. Skip n |> Seq.

ToList (firstList, secondList).

(I didn't like my previous answer so I deleted it) The first place to start when attacking list problems is to look at the List module which is filled with higher order functions which generalize many common problems and can give you succinct solutions. If you can't find anything suitable there, then you can look at the Seq module for solutions like @BrokenGlass demonstrated (but you can run into performance issues there). Next you'll want to consider recursion and pattern matching.

There are two kinds of recursion you'll have to consider when processing lists: tail and non-tail. There are trade-offs. Tail-recursive solutions involve using an accumulator to pass state around, allowing you to place the recursive call in the tail position and avoid stack-overflows with large lists.

But then you'll typically end up with a reversed list! For example, Tail-recursive gencut solution: let gencutTailRecursive n input = let rec gencut cur acc = function | hd::tl when cur gencut (cur+1) (hd::acc) tl | rest -> (List. Rev acc), rest //need to reverse accumulator!

Gencut 0 input Non-tail-recursive gencut solution: let gencutNonTailRecursive n input = let rec gencut cur = function | hd::tl when cur let x, y = gencut (cur+1) tl //stackoverflow with big lists! Hd::x, y | rest -> , rest gencut 0 input Once you have your gencut solution, it's really easy to define cut: let cut input = gencut ((List. Length input)/2) input.

1 nice explanation - but you didn't call out why one should aim for tail-recursion in the first place: they can be optimized by the compiler to not use any call stack space (since there is no state left on the stack you would have to get back to) so they allow for (essentially) infinite recursion. – BrokenGlass Feb 2 at 0:12 @BrokenGlass - Thanks! And you are absolutely right, that is an important point to make.

Thinking about how to answer this question, and reflecting on my own learning experience, I realized that it is really tough to explain something as basic has recursive list processing to an FP beginner since there are so many fundamentals you need to grasp first. – Stephen Swensen Feb 2 at 0:59.

Here's yet another way to do it using inbuilt library functions, which may or may not be easier to understand than some of the other answers. This solution also only requires one traversal across the input. My first thought after I looked at your problem was that you want something along the lines of List.

Partition, which splits a list into two lists based on a given predicate. However, in your case this predicate would be based on the index of the current element, which partition cannot handle, short of looking up the index for each element. We can accomplish creating our own equivalent of this behavior using a fold or foldBack.

I will use foldBack here as it means you won't have to reverse the lists afterward (see Stephens excellent answer). What we are going to do here is use the fold to provide our own index, along with the two output lists, all as the accumulator. Here is the generic function that will split your list into two lists based on n index: 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) List. Length) / 2 input |> gencut half I hope that can help you somewhat!

> 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 could avoid the index negation by supplying the length as the initial accumulator value and negating it on each cycle instead of increasing it - probably simpler that way :) let gencut n input = let results = List. FoldBack( fun elem acc-> let a,b,index = acc //decompose accumulator if index.

You can use List. Nth for random access and list comprehensions to generate a helper function: let Sublist x y data = for z in x..(y - 1) -> List. Nth data z This will return items x..y from data.

Using this you can easily generate gencut and cut functions (remember to check bounds on x and y) :).

I have the same Homework, this was my solution. I'm just a student and new in 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 | _, be :: listb -> cut (n - 1) (List. Rev (b :: lista )) listb cut n listb let cut xs = gencut((List.

Length xs) / 2, xs) Probably is not the best recursive solution, but it works. I think.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.