I've written a function which search through a list of int-list to return the index of the list with an specific length by using pattern-matching:

    let rec search x lst i = match lst with
   | [] -> raise(Failure "Not found")
   | hd :: tl -> if (List.length hd = x) then i else search x tl (i 1)
    ;;

For example:

utop # search 2 [ [1;2];[1;2;3] ] 0 ;;
- : int = 0

Is there a way to write a function with the same functionality using fold.left ?

CodePudding user response：

What does List.fold_left actually do?

It takes (in reverse order to the order of arguments) a list, an initial value, and a function that works on that initial value and the first element in he list. If the list is empty, it returns the initial value. Otherwise it uses he function to update the initial value by way of recursion and works on he tail of the list.

let rec fold_left f init lst =
  match lst with
  | [] -> init
  | x::xs -> fold_left f (f init x) xs

Now, what information do you need to keep track of as you iterate? The index. Easy enough.

But, what if you don't actually find a list of that length? You need to keep track of whether you've found one. So let's say we use a tuple of the index and a boolean flag.

Your function you pass to fold_left just needs to determine if a match has been found no update is necessary. Essentially we just no-op over the rest of the list. But, if we haven't found a match, then we need to test the current sublist's length and update the init value accordingly.

CodePudding user response：

@glennsl (in a comment) and @Chris already explained that you may use List.fold_left but that it’s not the right tool for the job since you want early termination. You can achieve it with OCaml features such as exceptions, but it’s somewhat hacky and inelegant.

I’ll just mention that there is a generic function in the standard library that matches your situation almost perfectly:

val find : ('a -> bool) -> 'a list -> 'a

find f l returns the first element of the list l that satisfies the predicate f.
Raises Not_found if there is no value that satisfies f in the list l.

However it does not return the index, unlike what you are asking for. This is a deliberate design choice in the standard library, because list indexing is inefficient (linear time) and you shouldn’t do it. If, after this cautionary words, you still want the index, it is easy to write a generic function find_with_index.

Another remark on your code: you can avoid computing the lengths of inner lists fully, thanks to the following standard function:

val compare_length_with : 'a list -> int -> int

Compare the length of a list to an integer. compare_length_with l len is equivalent to compare (length l) len, except that the computation stops after at most len iterations on the list.
Since 4.05.0

So instead of if List.length hd = x, you can do if List.compare_length_with hd x = 0.