How do you Iterate in OCaml?

Learning
1

Recently, while refreshing my knowledge of imperative algorithms and data structures, I found that OCaml’s loops and other default imperative iteration mechanisms are kinda crippled.

Most of the code I wrote before were some inductive data types and corresponding recursive functions, so I didn’t struggle, but writing an imperative code feels really inconvenient.

For example for loop can only iterate over the range of integers one way or another, without any way to break out of the loop (safe for raising Exit), nothing like Common Lisp’s return-from, you can’t even set a custom update statement, it’s either +1 or -1.

This wouldn’t be such a problem, if one could use custom iterators with loops, or even something SmallTalkish/Rubyish like 5.times closure.

I can see that in stdlib, in particular in Array and other imperative modules people just write recursive functions, and I find this code really hard to grasp in comparison with corresponding stuff in, say, Java (something like scheme’s “auto-launching” let would make it a little bit better).

So, how do you write imperative iterating code in OCaml? Do you introduce your own iterators? Do people implement ranges and other stuff like this? Do you use Seq as standard iterating interface?

2

Note that there is a general-purpose while loop at your disposal as well.

Cheers,
Nicolás

1 Like
3

This is a philosophical difference. In all languages descended from Scheme (or taking some intellectual heritage from Scheme) the idea is that (tail-)recursion is superior to iteration, and tail-recursion-optimization is implemented in the compiler to support this. The entire “ethos” encourages writing iteration combinators of various sorts, or using recursion directly.

I could make the arguments for why this is superior to the Java way of doing this, but really, it just depends on how you see the world: does iteration come prior to recursion? Or vice versa?

I distinctly remember in 1986 in my first PL class, learning scheme and learning this idea:it was pretty alien at the time for a C jock, I can assure you. So it really is a -choice- of how to see things.

ETA2: I see I didn’t answer all your questions. [Disclaimer: I’m not an authority, just somebody who was there when this stuff was esoteric, and saw it enter the mainstream. [heh, as if it’s not still esoteric, giggle]]

(1) vs. smalltalk/ruby iterators: Actually, you can think of the iteration constructs in Scheme-like languages as being more-or-less like those of Ruby, I think. The syntax support isn’t there, but in this community that isn’t seen as a problem. Your example of “5.times.closure” is a good one: it’s pretty straightforward to write a Range.t type (to capture [n…m) range iteration) with all the standard iteration combinators, and lots of us do stuff like that as a matter of course.
(2) built-in loop-break vs. exceptions: IIRC, in data-flow analysis these are equivalent in complexity. And furthermore, languages like ML always implement really cheap exceptions, so breaking out of a loop with a raise is supposed to be as cheap as doing it with a “break” in other languages. But more importantly, the lack of lots of niceties for for-loops, I think, is meant to encourage the programmer to use “real iterators” instead. You know, recursiion. Because there, to break out of a tail-recursive loop is … obvious, simple, and cost-less.

2 Likes
4

Probably, you shouldn’t do but…

let counter = ref 5;;
while begin
  print_endline "Hello from an imperative loop";
  decr counter;
  !counter <> 0
end do () done
2 Likes
5

To a certain degree, I see the limitation of the OCaml for loop as a feature rather than a bug. It pushes you towards other choices that clarify the pattern:

  1. Are you creating 1-1 mapping of the iterated array? Use Array.map.
  2. Are you computing one or more values while iterating? Try to separate your effects from the computation, and use Array.fold and its variants.
  3. If it’s a pure iteration with effects, Seq is a good choice, but Iter is more efficient, and works well with Containers.
  4. If you need early exit from the loop, Iter's take_while does the job, and keeps the pattern clear:
Array.to_iter |> Iter.take_while (fun x -> x < 3) |> Iter.iter (fun x -> print x)
  1. You always have a recursive loop as a fallback. Personally I only do that in the case of pure iteration when I have to (e.g. for performance reasons).
3 Likes