2/20/2021
Because I'm taking both an algs class and a coding class (Ocaml-based) with the same professor, I was not suprised to find my first project to be using OCaml to write mergesort - Both are concepts/method introduced in either class.
To begin with, an algs is provided, and I hardly looked at it because I've done mergesort (kinda) in java before (leetcode 23). So I went straight to building two helper functions that would make my life eaiser.
First is split, which takes in 3 arguments listU; listL; listR. It simply split listU's elements into listL and listR. It might be easy to notice that in some cases you have to split the list into 3 part, [first; second; others], in order to access first and second for the recursive calls. However, dispite the fact that OCaml is kind enough for us to let us split the list easy with :: operator, it wouldn't allow us to splitting it further. Thus, what I did is I called match right after I split the list to first and others, and thus split the others further into second and others, sovled the issue. Here's the code for split: (Note: It is tail recursive- I think) Updates: No need for this nested match crap, I can simply do it with _ :: _ :: list, I cannot accept :(((((
Now let's talk about merge. So mergesort is actually making multiple sort between two lists, and recursively achevied sorted. Thus what we need to write is a herlper that merges two list together. mergeTwo takes in three arguments listU; listL; listR, and there are serval situations for listL and listR (details in comments). Not really a lot of to talk about for this. Should be tail- recursive, I think. Here's the code:
For mergesort that runs the who program, I'm running into problems. The algs itself was cool, but I'm getting OCaml's complain about pattern-matching not being exhaustive:
I'm having trouble understand this (_::_::....) something here, why is there a "|" inside the pattern matching? What the hell is that () around this pattern anyway? I can use short curcit to get around this problem by adding a general case like [_] or something in the end, but the OCaml would give me something saying "this pattern was never used".
A way of solving this is simply adding the pattern into the code, since it won't show up anyway (I think), but it looks so ugly:
Finally, I have to combine [] pattern with the ugly one to make it less ugly, which turns out fine I think. Here's the final code: (Note: tail recursive? I think)
I guess it is still pretty elegent? I really like OCaml in a way that it is very simple, and elegent. After I finished the function, I couldn't even believe this is it, so snappy for only 6 lines! so nice!
Here is the final edition of mergesort:
新用的这个插件显示颜色是真的漂亮
Until next time;;
