CODEWITHSUNDEEP
listocamlfold
jonnyd42
jonnyd42

Reputation: 500

Generating list of integers in OCaml without recursion

How can I use one of the fold functions to generate a list of integers from 0 to a value n-1? I'm confused about how to get fold_right to return a list rather than returning just an accumulated value.

This is for a helper function that I'm trying to define to solve a larger problem. Here is my attempt:

-I know the base case has to be a list containing only zero, because I do not want to add anything less than zero.
-I know that I need to decrement the value n so that I can put numbers from n-1 to 0 in the list.

let buildList n = 
  let ibuildList elem list =
    list@[n-1]
  in List.fold_right ibuildList n [0];;

But I get an error underscoring "n" in the last line saying that the expression has type int but an expression was expected of type 'a list. Isn't n an integer that I'm turning into a list via [n-1]? Where did I go wrong?

Upvotes: 1

Views: 3763

Answers (2)

Anton Trunov
Anton Trunov

Reputation: 15404

An alternative version, using the standard Stream module:

(* an infinite stream of natural numbers, starting from 0 *)
let nats =
  let rec nats_from n = [< 'n; nats_from (n + 1) >]  (* extra syntax *)
  in nats_from 0

(* the first n natural numbers: [0; n-1] *)
let range n = Stream.npeek n nats

The piece [< 'n; nats_from (n + 1) >] represents a lazy list with n as its head and the next natural numbers as its tail. Stream.npeek n stream consumes the first n elements of stream and returns them as a list.

Tests with utop:

utop # #load "dynlink.cma";; (* you need these to work with *) 
utop # #load "camlp4o.cma";; (* the Stream's syntactic extension *)

utop # range 1;;
- : int list = [0]    

utop # range 5;;
- : int list = [0; 1; 2; 3; 4]

utop # range 10;;
- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]

If you'd like to compile it, use the following commands (you need to use the camplp4o preprocessor):

$ ocamlc -pp camlp4o <filename>.ml

or

$ ocamlopt -pp camlp4o <filename>.ml

Upvotes: 1

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66818

Very sorry, I missed at least one step of the reasoning.

A fold is for traversing a collection. Since you want to generate a list and you just have n, not a collection, you can't really use fold in any reasonable way. In fact, what you want to do is more like an unfold. I.e., you want to unfold your n into a list.

It's easy to write this function, but not easy to write it using a fold.

Here's an implementation of unfold in OCaml:

let rec unfold_right f init =
    match f init with
    | None -> []
    | Some (x, next) -> x :: unfold_right f next

Here's how to use unfold_right to generate a list of ints:

let range n =
    let irange x = if x > n then None else Some (x, x + 1) in
    unfold_right irange 1

Here's how it looks when you run range:

# range 0;;
- : int list = []
# range 8;; 
- : int list = [1; 2; 3; 4; 5; 6; 7; 8]
# range 5;;
- : int list = [1; 2; 3; 4; 5]

Upvotes: 3

Related Questions