According to this previous answer
You could implement List.map
like this:
let rec map project = function
| [] -> []
| head :: tail ->
project head :: map project tail ;;
but instead, it is implemented like this:
let rec map project = function
| [] -> []
| head :: tail ->
let result = project head in
result :: map project tail ;;
They say that it is done this way to make sure the projection function is called in the expected order in case it has side effects, e.g.
map print_int [1;2;3] ;;
should print 123
, but the first implementation would print 321
. However, when I test both of them myself in OCaml and F#, they produce exactly the same 123
result.
(Note that I am testing this in the OCaml and F# REPLs--Nick in the comments suggests this might be the cause of my inability to reproduce, but why?)
What am I misunderstanding? Can someone elaborate why they should produce different orders and how I can reproduce? This runs contrary to my previous understanding of OCaml code I've written in the past so this was surprising to me and I want to make sure not to repeat the mistake. When I read the two, I read it as exactly the same thing with an extraneous intermediary binding.
My only guess is that the order of expression evaluation using cons is right to left, but that seems very odd?
This is being done purely as research to better understand how OCaml executes code, I don't really need to create my own List.map
for production code.
Ocaml's List. map function is the same as the map defined above. The map function is a list transformer: it takes a list as an input and returns another list as an output.
Note that List. rev is tail-recursive. This idea is to have the accumulated prefix list be represented by a function acc that, when applied to an argument list ys , returns the prefix list prepended to ys .
Hence, to truncate a list, you need to create a new list that contains only the first elements (this is the only way to get the desired truncated list). let truncate : 'a -> 'a list -> 'a list = fun elt queue -> ...
Regarding the :: symbol - as already mentioned, it is used to create lists from a single element and a list ( 1::[2;3] creates a list [1;2;3] ). It is however worth noting that the symbol can be used in two different ways and it is also interpreted in two different ways by the compiler.
The point is that the order of function application in OCaml is unspecified, not that it will be in some specific undesired order.
When evaluating this expression:
project head :: map project tail
OCaml is allowed to evaluate project head
first or it can evaluate map project tail
first. Which one it chooses to do is unspecified. (In theory it would probably be admissible for the order to be different for different calls.) Since you want a specified order, you need to use the form with let
.
The fact that the order is unspecified is documented in Section 6.7 of the OCaml manual. See the section Function application:
The order in which the expressions expr, argument1, …, argumentn are evaluated is not specified.
(The claim that the evaluation order is unspecified isn't something you can test. No number of cases of a particular order prove that that order is always going to be chosen.)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With