1

So, I found out that Ocaml supports the creation of circular lists using let rec.

utop # let rec ones = 1::ones;;
val ones : int list = [1; <cycle>]

That is pretty neat, and it even prints out in utop without blowing up.

But when I try to use List.map on this kind of data it does blow up:

utop # let twos = List.map ((+) 1) ones;;
Stack overflow during evaluation (looping recursion?).
Raised by primitive operation at Stdlib__List.map in file "list.ml", line 92, characters 32-39
Called from Stdlib__List.map in file "list.ml", line 92, characters 32-39
...

That is somewhat disapointing, though not totally unexpected.

Now the question, would it be possible to implement a 'better' map function that can handle this properly. I.e. you would do something like:

let twos = betterMap ((+) 1) ones;;

And instead of blowing up it would be able to detect the cycle properly and produce:

val twos : int list = [2; <cycle>]

Since the list of ones, though looping back on itself, is effectively a finite structure, it feels like this should be possible. But how?

Kris
  • 3,898
  • 1
  • 23
  • 32
  • 1
    Possibly useful: https://stackoverflow.com/questions/44367761/what-is-cycle-in-data – Chris Apr 30 '22 at 01:11
  • Another similar question: https://stackoverflow.com/questions/26475516/how-do-i-write-a-function-to-create-a-circular-version-of-a-list-in-ocaml. I gather the fundamental problem is creation of cycles via function calls. And it seems such a thing is 'forbidden' by the rules of 'let rec'. So the only way it is possible then to create a cycle is probably via a mutation. Since ocaml list are immutable, this is only possible via (ab)using a module called `Obj` which allows mucking with internal representaion of Ocaml values. So you can use it to mutate something immutable. – Kris Apr 30 '22 at 01:32
  • Maybe the simplest solution would be working on sequences instead. – jthulhu Apr 30 '22 at 04:54

1 Answers1

1

It is only possible to create cyclic lists when the cycle is statistically known. It is thus impossible to create a map function that works on any cyclic lists without knowing in advance the topology of cycles in the list. For instance, this function works for lists that are 1-cycle:

let map_1_cycle f = function
  | [] -> []
  | a :: l ->
     let rec answer = f a :: answer in
     answer

The generic solution is to use sequences since as a form of lazy list, they have a much better support for infinite sequences of elements:

let ones = Seq.repeat 1
let twos = Seq.map ((+) 1) ones
octachron
  • 17,178
  • 2
  • 16
  • 23
  • Technically speaking I guess that might not be correct as we see from this answer https://stackoverflow.com/a/35420975/2141091 that there is a way to make cyclic lists using `Obj` module. Very hacky, so it can be debated if that is even really 'part of the ocaml language'. – Kris Apr 30 '22 at 15:57
  • The difference between using a 'Seq' like that and the hypothetical `betterMap` function I had in mind is that the `Seq.map` destroys / looses the cyclic nature of the data (i.e. it unrolls it into a truly infinite sequence of twos. It is lazy computed, so it remains finite, but as you look at more and more values in that sequence it consumes more and more memory. With `betterMap` you put in a cycle and get out a cycle. It would be a 'true' isomorphic mapping on cyclic data. Given that ocaml has support for 'cyclic' immutable data, it feels like this *should* somehow be possible. – Kris Apr 30 '22 at 16:02
  • If it is truly not possible (without `Obj` module) to make an isomoprhic copy of a cyclic data structure then arguably they are of very limited use. (BTW: to me a 'cyclic' structure is something different from a 'infinite' structure. E.g. the 'Sequence' of all natural numbers is infitite. But a graph (or list, or any kind of data) with cycles in it, is not. There are many situations in which cyclic data make sense as representation of something, for example something like a DFA, a dependency graph etc. Having the ability to 'map' over such data and preserve the cyclic nature would be useful. – Kris Apr 30 '22 at 16:19
  • `Obj` is not part of the language. It is mostly intended to be used by higher-level programming language with a stronger type system that are using OCaml as a back-end (aka Coq). The `Seq` version does not consume more memory if you are not storing intermediary values. There is no issue with representing graphs or other cyclic data structure using either mutable values, or by separating the vertices and the edges. Constructing immutable recursive data structure is just not a good way to do so. – octachron Apr 30 '22 at 17:04
  • I agree with most of what you say, but I think the 'Seq' does use more memory. When you access the first 10 (just to name a number) elements in a 'infinite sequence of ones or two' it's representation becomes 10 nodes large. I.e. it isn't 'cyclic' at all instead it is 'infinitely expanding'. It effectively repeats the data x number of times, instead of pointing back to itself. So they really are quite different in that sense. You also said "if you are not storing intermediary values"... I don't actually know what you mean by that. – Kris Apr 30 '22 at 19:23
  • Another way in which 'Seq.map' is different from my hypotethical 'List.betterMap' would be that it repeatedly calls the function 'f'. Assuming that this function is 'expensive' to call then we'd rather not call it multiple times when there is really just one element in the cycle. Again this points at a difference between something cyclic versus something that is infinitely expanding on demand. I agree with you though, constructing immutable recursive data isn't a good way to deal with cyclic things *in Ocaml*, since it doesn't provide a good way to actually work with this data. – Kris Apr 30 '22 at 19:31
  • The source code of Ocaml `Seq` module makes for some interesting reading to see how they handle these sorts of things. Quite a neat and interesting module. A nice module to use as well for some insight into implementation tricks. – Kris Apr 30 '22 at 20:06
  • Cyclic links are more useful with mutable data structures, which is also the only way to manipulate them. That you can construct a circular list is more of an oops. There just is no reason to specifically catch this use case of `let rec`. It's not even wrong, just basically useless. The mentioned Obj module allows turning a list into a mutable structure and back or just overwriting the value directly. It circumvents the type system in very unsafe ways do let you do hacks like that. – Goswin von Brederlow May 06 '22 at 15:39