What does :: and ' mean in oCaml?

Question

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

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

Answer 1

The ' is simply 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 "the list that has foo as its first element, followed by the elements of bar". So the meaning of the match statement is:

If xs is the empty list, the value is 0. If xs is the list containing the item x followed by the items in xs' the value is x + sum xs'. Since x and xs' are fresh variables, this has the effect that for any non empty list, x will be assigned the value of the first element and xs' will be assigned the list containing all other elements.

Answer 2

I think sepp2k already answered most of the question, but I'd like to add a couple of points that may clarify how F#/OCaml compiler interprets the code and explain some common uses.

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

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

• Another frequent use is when declaring a local utility function that implements the functionality and takes an additional parameter (typically, 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 there is usually a better name for the function/value, so I try to avoid using ' when writing code (I think it isn't particularly readable and moreover, it doesn't colorize correctly on StackOverflow!)

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.

When creating a list, you use it as an operator that constructs a list (just like when you use + to add two numbers). However, when you use it in the match construct, it is used as a pattern, which is a different syntactic category - the pattern 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 3

It's idiomatic in ML-family languages to name a variable foo' to indicate that it's somewhat related to another variable foo, especially in recursions like your code sample. Just like in imperative languages you use i, j for loop indices. This naming convention may be a little surprising since ' is typically an illegal symbol for identifiers in C-like languages.

Answer 4

Like others have said, the ' is a carryover from mathematics where x' would be said as "x prime"