Merge sort

Hello again,

Okay, Ass2 Q5. Does anyone know how to chop a list in half? We can use [First|Rest] to get the first element of a list, and difference lists can be used to get the last element, but how do you chop it in half?

conc(LeftBit, RightBit, List) doesn't guarantee the halves will be the same size, and we've already established that it's not very efficient.

My best guess is that there's a sneaky way to use difference lists which can get you 2 similarly-sized halves, but I honestly can't see a solution. Please could someone throw me a bone here? Ta

perhaps get the length of the list and then divide that number by 2? Don't think we have to use difference lists for this question.

could you do the bagof, setof and findall questions??

Hi Celene,

Yes, you're right. I figured that the length was necessary, but couldn't work out a better way to split the list other than conc, so that's the way I've done it. It's a monster though... so I hope I don't get marked down for efficiency.

Yeah, I managed to get Q4. I din't use findall at all, and (b) was easier to do without using the special procedures. Do you need help with anything in particular?

This is sort of cheating I guess, but it was the simplest/most efficient way I could think of and technically satisfys the criteria of what it's supposed to do.

divide([],[],[]).
divide([],[],[],_).
divide([H|T],L1,[H|L2],_):-divide(T,L1,L2).
divide([H|T],[H|L1],L2):-divide(T,L1,L2,_).%split a list into two halves (odd and even not down the middle)

what do you think?

I managed to split it using length/2. It's not the most efficient solution, but at least it works.