CODEWITHSUNDEEP
recursionocamlfold
J_code
J_code

Reputation: 347

Folding a list in OCaml

In OCaml, a typical fold function looks like this:

let rec fold (combine: 'a -> 'b -> 'b) (base: 'b) (l: 'a list) : 'b =
  begin match l with
  | [] -> base
  | x :: xs -> combine x (fold combine base xs)
  end

For those familiar with OCaml (unlike me), it should be pretty straightforward what it's doing.

I'm writing a function that returns true when all items in the list satisfy the condition: if condition x is true for all x in some list l. However I'm implementing the function using a fold function and I'm stuck. Specifically I don't know what the list should return. I know that ideally the condition should be applied to every item in the list but I have no idea how the syntax should look. x && acc works but it fails a very simply test (shown below)

let test () : bool =
  not (for_all (fun x -> x > 0) [1; 2; -5; -33; 2])
;; run_test "for_all: multiple elements; returns false" test

Here is my preliminary attempt. Any help is appreciated:

let  for_all (pred: 'a -> bool) (l: 'a list) : bool =
fold (fun(x:'a)(acc: bool)->  _?_&&_?_  )false l

Upvotes: 3

Views: 3059

Answers (2)

Chris
Chris

Reputation: 36571

Your fold works fine.

But you are operating under a faulty premise about how for_all should work. You start with your initial value on false, but for_all is checking that a condition holds true for every element. It only needs to find one element for which that doesn't hold true to know that the entire thing is false.

On each iterative call, if the accumulator is already false we know we can just propagate that to the end of the fold. If it's true, we update the accumulator to the result of calling the predicate on the current value.

let for_all predicate lt =
  fold (fun x acc -> if not acc then acc else predicate x) true lst

This is an inherently inefficient way to implement for_all because even if the very first iteration returns false we still have to traverse the entire list.

By writing this without fold we can exit the recursion as soon as the false condition is found.

let rec for_all predicate = function
  | [] -> true
  | x::_ when not (predicate x) -> false
  | _::xs -> for_all predicate xs

Upvotes: 0

Ulugbek Abdullaev
Ulugbek Abdullaev

Reputation: 435

let rec fold (combine: 'a -> 'b -> 'b) (base: 'b) (l: 'a list) : 'b =
  match l with
  | [] -> base
  | x::xs -> combine x (fold combine base xs)

let for_all (pred: 'a -> bool) (lst: 'a list) =
  let combine x accum =
    (pred x) && accum
  in
  fold combine true lst

Your combine function should not do x && base because elements of the list are not usually bool. You want your predicate function first evaluate the element to bool, then you "and" it with the accumulator.

There is no need for begin and end in fold. You can just pattern match with match <identifier> with.

There are two widespread types of fold: fold_left and fold_right. You're are using fold_right, which, basically, goes through the whole list and begins "combining" from the end of the list to the front. This is not tail-recursive.

fold_left, on the other hand goes from the front of the list and combines every element with the accumulator right away. This does not "eat up" your stack by a number of recursive function calls.

Upvotes: 2

Related Questions