Using fold to check if a list is divisible by an int and return bool list ocaml

Question

I am trying to implement a function which takes in an int and a list of numbers, and check if all elements of the list is divisible by the int, for example:div_by_x 2 [1;3;4;8;0] = [false;false;true;true;true] I have a helper function which just returns true or false when viable:

let divisible x i = 
     if i mod x = 0 then true else false;;

With that, I have already implemented a working recursive div function, which is:

let rec div_by_x x y = match y with 
    [] -> [] 
   | (hd :: tl) -> 
      let l1 = div_by_x x tl in divisible x hd :: l1;;

But now I am trying to implement div_by_x with the fold function, defined as:

let rec fold f a l = match l with
   [] -> a
   | (h::t) -> fold f (f a h) t
;;

I am kinda stuck on how to make the list while keeping the on going list. So far I have

let div_by_x x y= fold divisible x y [] y;;

which doesnt seem to work and yells at me with: "

Error: This expression has type int -> int -> bool but an expression was expected of type ('a -> 'b -> 'c) -> 'd -> 'a -> 'b -> 'c Type int is not compatible with type 'a -> 'b -> 'c "

Any help? Thanks!

Not the answer to your question, but if expression then true else false can be replaced by expression alone. — PatJ
If you look carefully at your problem, you'll notice that you are trying to apply divisible x to each element of the list. This can be accomplished using map. You now have to implement map in terms of fold. :) — gallais

Jeffrey Scofield Jeffrey Scofield · Accepted Answer · 2015-10-01T06:25:05

You want to fold a function that does one incremental step of computation. For your problem, one incremental step consists of determining divisibility and adding the resulting boolean to a list. You're trying to fold a function that just determines divisibility.

The first thing to do, I think, is to figure out what your folded function should actually look like. If you look at the type of your fold you can see the type of the function you need:

# let rec fold f a l = match l with
   | [] -> a
   | (h::t) -> fold f (f a h) t ;;
val fold : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

The folded function should (in general) have type 'a -> 'b -> 'a. In other words, it takes the accumulated answer so far and the next element of the input list, then returns a new accumulated answer.

For your problem the specific type will be bool list -> int -> bool list.

Your function divisible has type int -> int -> bool, which isn't very close to what you need.

When you figure out what the function should look like, the call might look like this:

let div_by_x x y =
    let myfun a b = <<test b for divisibility by x, add to a>> in
    fold myfun [] y

If you want to learn about curried functions (which is worth knowing about), your definitions could look like this:

let myfun x a b = . . .

let div_by_x x y = fold (myfun x) [] y

(Since your fold is a left fold, you may find that it produces a list in reverse order.)

Using fold to check if a list is divisible by an int and return bool list ocaml

1 Answers