Notes (OFVB 04/31): Making Lists
see lists.ml
Inner recursion functions shouldn’t be exposed outside of the scope of the function they’re being used for. Beter to define go function with a let.
Making take and drop total functions only requires adding an additional pattern to match on. Nested matching is a little clunkier than how Haskell does it though, so I hope there’s more advanced syntax to learn later on.
Questions
1
Type of evens is a' list -> a' list
2
We certainly can write a tail-recursive version of this, but I think it’s more interesting to use an inner function to give us an explicit accumulator. Really this should be done with a fold, but we haven’t covered that yet.
4
Here’s a case where tail recursion makes sense.
6
Type of make_set is a' list -> a' list
7
rev is inefficient because @ is O(n) with respect to the length of t, every time it’s called. Because @ gets called on every ::, this makes rev O(n^2).
My reverse function in lists.ml, is O(n) with respect to the length of the list since it calls :: (which is O(1)) once for every list element.