« sorting things » sample in OVB : how does it work?

Learning
1

Hello,

I’m learning OCaml. I’m following recommanded book « Ocaml from the very beginning ».
In the beginning of the chapter #5 (sorting things) i see:

let rec sort l =
  match l with
  [] -> [] 
| h::t -> insert h (sort t) (* why sort t ? Will it call sort until no elements left ? *)

let rec insert x l =
  match l with
  [] -> [x] 
| h::t -> 
    if x <= h 
    then x :: h :: t 
    else h :: insert x t

It raises many questions for me…
I’ve tried in the sort function to call insert like this: insert h t and it works too.
I was thinking that the original call insert h (sort h) will sort also the existing list, but that’s not the case. Unordered list passed as parameter stays unordered:

insert 10 [3;8;99;5;18];;

: int list = [3; 8; 10; 99; 5; 18]

(called with original insert h (sort h))

And why can I call a two parameters function without parenthesis ? I was expecting to call like this: insert (h t)

Thank you for your help.

2

If you do insert h t (without the recursive call to sort t), if you call sort [4; 3; 2] you will end up with [3; 4; 2], which is not sorted. That is, 4 was correctly inserted, but the tail of the list [3; 2] still needs to be sorted.

Yes, this is precisely why you need to call sort on the tail of the list recursively.

This is the traditional syntax in ML-style languages. It helps with partial application, whereby you can apply a two-argument function to its first argument and obtain a function of the second argument only, eg insert h : int list -> int list.

Cheers,
Nicolas

2 Likes
3

insert places x where it should be in a sorted l. When you pass an unsorted l, it still tries as you can see: the 10 is placed after 8 and not before it or before the 3.

insert by itself isn’t a sorting function, but it can be used to sort. sort calls it once per element of the list passed. With a type annotation and #trace sort;; the calls look like this:

# sort [3;10;8];;
sort <-- [3; 10; 8]
sort <-- [10; 8]
sort <-- [8]
sort <-- []
sort --> []
sort --> [8]
sort --> [8; 10]
sort --> [3; 8; 10]
- : int list = [3; 8; 10]
1 Like
4

Ok, i’ve understood why i didn’t understood.

I’m following explainations of OVB book, and try to implement by not looking at the « answer ». Then, i’m looking at the listing following explainations , to correct all those weirds OCaml messages.

In the explaination, author begins to define sort function, and then insert. In the listing, it does the contrary.

So i’ve implemented in this order , and #use it in utop. As sort needs insert, and insert does not exists at this step, i had to invert functions. But later, sort was already defined, so whatever changes i made in it , was not taken in account. and the call to insert was always insert h t, even if i change it to insert h (sort h). I was seeing no differences after a reload in utop, thus my first post here.

Simple illustration of my problem:

module test.ml, compute a²

let first a = a*a
let second = first 2

in utop, everything’s fine:

# #use "test.ml";;
val first : int -> int = <fun>
val second : int = 4

Let’s change order in test.ml, and first becomes a³

let second = first 2
let first a = a*a*a

and reload it:

# #use "test.ml";;
val second : int = 4
val first : int -> int = <fun>

fun ? No fun.

5

I think what you are missing is that you aren’t assigning a new value to the same variable, you are shadowing the old name.

─( 13:34:20 )─< command 0 >──────────────────────────────────────{ counter: 0 }─
utop # let foo x = x * 2;;
val foo : int -> int = <fun>
─( 13:34:20 )─< command 1 >──────────────────────────────────────{ counter: 0 }─
utop # let bar x = foo x + 1;;
val bar : int -> int = <fun>
─( 13:34:29 )─< command 2 >──────────────────────────────────────{ counter: 0 }─
utop # let foo x = x * 3;;
val foo : int -> int = <fun>
─( 13:34:51 )─< command 3 >──────────────────────────────────────{ counter: 0 }─
utop # foo 10;;
- : int = 30
─( 13:34:57 )─< command 4 >──────────────────────────────────────{ counter: 0 }─
utop # bar 10;;
- : int = 21

So - I am not overwriting that first foo, I’m defining a new foo which shadows or masks the first one. But bar is referring to the original one because it is still there. It isn’t a variable it is a named value.

If you changed your example to have two files “test1.ml” and “test2.ml” perhaps that would make it more obvious. The values in each file would be loaded into the REPL and shadow any previous ones.

If you shadow a “variable” in a file you should get a warning either from your editor or when you try to compile it. In normal coding, shadowing is mostly an accident.

1 Like
6

I think i understand, thank you. As you have probably guessed, i was expecting this behaviour:

Lua 5.4.8 Copyright (C) 1994-2025 Lua.org, PUC-Rio

fun=function (a) return a*a end
test=function(a) return fun(a) end
test(2)
4
fun=function (a) return a*a*a end
test(2)
8

7

In OCaml, you can’t change the value of something defined by let. Then

let foo x = x*x
let bar x = foo x
let foo x = x*x*x

Declares two functions foo. Bar uses the first.

If you want to “change” foo, you have to write:

let foo = ref (fun x-> x*x)
let bar x = !foo x
foo := (fun x -> x*x*x)
1 Like
8

Thank you, i must confess i had tried to implement it with « ref ».

But i don’t know enough OCaml to do this alone.

Now i stop, before « shadowing » the original topic.

Very instructive for me , indeed. For the moment , each answer raises more questions for me, so i will read more and try to have a global comprehension before next questions.

NOTE: i wanted to edit the topic title and add [SOLVED] but it seems it’s not possible (or i cannot do that as i don’t have all my scout badges yet)

9

If this is your first real exposure to (a) functional programming and/or (b) an ML or lisp language then what I have found works best for me is to move forward in very small steps. That way if you go off-course then you know exactly where the error must be.

This is especially important with type errors where if your mental model doesn’t match the compiler the errors can be very confusing.

Luckily OCaml not only has utop but also a very fast compiler, so checking code often is cheap.

1 Like
10

You can get OCaml’s behavior in Lua, and in many similar languages, at function scope:

local function f()
  local fun = function (a) return a*a end
  local test = function (a) return fun(a) end
  print(test(2))
  local fun = function (a) return a*a*a end
  print(test(2))
end
f()  -- prints 4 both times

as toplevel definitions are treated specially in these languages, and are really mutating a namespace, with further references dynamically referring through that namespace rather than captured when referenced. In Python you can see that namespace with globals(), and in Python you can still speed up code by lifting a frequently referenced variable into function scope, to avoid slower lookup.

It’s similar to this OCaml, interactively:

# let ns = Hashtbl.create 0;;
val ns : ('_weak1, '_weak2) Hashtbl.t = <abstr>
# Hashtbl.replace ns "f" (fun a -> a*a);;
- : unit = ()
# Hashtbl.replace ns "test" (fun a -> (Hashtbl.find ns "f") a);;
- : unit = ()
# (Hashtbl.find ns "test") 2;;
- : int = 4
# Hashtbl.replace ns "f" (fun a -> a*a*a);;
- : unit = ()
# (Hashtbl.find ns "test") 2;;
- : int = 8

although ref would work better if you really want this behavior:

let f = ref (fun a -> a * a)
let test a = !f a
let () =
  Printf.printf "%d\n" (test 2);
  (f := fun a -> a * a * a);
  Printf.printf "%d\n" (test 2)
2 Likes