What does :: mean and in oCaml?

Question

What does x :: xs' mean? I do not have much functional experience, but IIRC in F # 1 :: 2 :: 3 :: [] ;; creates an array of [1,2,3] so what does? do?

 let rec sum xs = match xs with | [] -> 0 | x :: xs' -> x + sum xs' 

Answer 1

I think sepp2k already answered most of the questions, but I would like to add a couple of points that can explain how the F # / OCaml compiler interprets the code and explains some common uses.

As for the symbol ' - this is only part of the name (a valid identifier begins with a letter and then contains one or more letters, numbers or characters ' ). It is usually used if you have a function or value that is very similar to some other, but in some way new or changed.

• In your example, xs is a list to be summed, and pattern matching decomposes the list and gives you a new list (without the first element) that you need to sum, so it's called xs'

• Another common use is to declare a function of a local utility that implements functionality and accepts an additional parameter (usually when writing tail recursive code):

   let sum list = let rec sum' list res = match list with | [] -> res | x::xs -> sum' xs (res + x) sum' list 0 

However, I think that there is usually a better name for the function / value, so I try to avoid using ' when writing code (I think this is not particularly readable and, moreover, it does not paint correctly on StackOverflow!)

As for the symbol :: - as already mentioned, it is used to create lists from one element and a list ( 1::[2;3] creates a list [1;2;3] ). However, it is worth noting that a symbol can be used in two different ways, and it is also interpreted by the compiler in two different ways.

When creating a list, you use it as an operator that creates a list (the same as when using + to add two numbers). However, when you use it in a match construct, it is used as a template, which is another syntax category - the template is used to decompose the list into an element and the remainder, and it succeeds for any non-empty list

 // operator let x = 0 let xs = [1;2;3] let list = x::xs // pattern match list with | y::ys -> // ... 

Answer 2

"This is just part of the variable name. And yes foo :: bar , where foo is an element of type a and bar is a list of type a, means" a list that has foo as its first element, followed by elements of the bar. " Thus, the value of the match expression:

If xs is an empty list, the value is 0. If xs is a list containing x, followed by elements in xs' , the value is x + sum xs' . Since x and xs' are new variables, this means that for any non-empty list x value of the first element will be assigned, and xs' will be assigned a list containing all other elements.

Answer 3

Like others, “transfer from math, where x” will be denoted as “x prime”

Answer 4

It is idiomatic in the languages ​​of the ML family to name the variable foo' to indicate that it is somewhat related to another variable foo , especially in recursions like your sample code. As in imperative languages, you use i , j for loop indices. This naming convention can be a bit surprising, since ' usually an illegal character for identifiers in C-type languages.

Answer 5

What does x :: xs' mean?

If you have two variables called x and xs' , then x :: xs' creates a new list with x added to the beginning of xs' .

I do not have much functional experience, but IIRC in F # 1 :: 2 :: 3 :: [] ;; creates an array of [1,2,3]

Not really. This is a list.

so what does? do?

It is considered as an alphabetical symbol, so the following is equivalent:

 let rec sum xs = match xs with | [] -> 0 | x :: ys -> x + sum ys 

Note that :: is technically a type constructor, so you can use it in both templates and expressions.