I want to understand how Array.length is implemented. I managed to write it with Array.fold_left:

let length a = Array.fold_left (fun x _ -> x   1) 0 a

However in the standard library, fold_left uses length so that can't be it. For length there is just this line in the stdlib which I don't understand:

external length : 'a array -> int = "%array_length"

How can I write length without usingfold_left?

EDIT:

I tried to do it with pattern matching, however it is not exhaustive, how can I make the matching more precise? (The aim is to remove the last element and return i 1 when only one element is left)

let length a = 
         let rec aux arr i = 
         match arr with
           | [|h|] -> i 1
           | [|h;t|] -> aux [|h|] (i 1)
        in aux a 0;;

CodePudding user response：

For length there is just this line in the stdlib which I don't understand:

The external keyword indicates that this function is implemented in C, and "%array_length" is the C symbol naming this function. The OCaml runtime is implemented in C and some types, like arrays, are built-in (also called primitives).

See for example Implementing primitives in Chapter 20: Interfacing C with OCaml

I tried to do it with pattern matching, however it is not exhaustive, how can I make the matching more precise

Note that OCaml tells you which pattern is not matched:

Here is an example of a case that is not matched:
[|  |]

So you have to account for empty vectors as well.

CodePudding user response：

The array type is a primitive type, like the int type. The implementation of many primitives functions on those primitive type is done with either C functions or compiler primitives.

The Array.length function belongs to the compiler primitive category and it is defined in the standard library by:

external length : 'a array -> int = "%array_length"

Here, this declaration bind the value length to the compiler primitive %array_length (compiler primitive names start with a % symbol) with type 'a array -> int. The compiler translates such compiler primitive to a lower level implementation during the translation process from the source code to either native code or bytecode.

In other words, you cannot reimplement Array.length or the array type in general in an efficient way yourself because this type is a basic building block defined by the compiler itself.