使用fold_left搜索OCAML中特定长度的列表

发布于 2025-02-07 21:36:13 字数 402 浏览 4 评论 0原文

我已经写了一个函数，该功能通过int-list列表进行搜索，以使用模式匹配使用特定长度返回列表的索引：

    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)
    ;;

例如：

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

有没有一种方法可以使用fold.left ？

原文

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 ?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

最终幸福 2025-02-14 21:36:13

list.fold_left实际做什么？

它（以参数的顺序相反顺序）列表，一个初始值以及在列表中使用的函数和一个函数。如果列表为空，则返回初始值。否则，它使用该功能通过递归方式更新初始值，并在列表的尾部工作。

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

现在，您需要在迭代时跟踪哪些信息？索引。足够容易。

但是，如果您实际上找不到该长度的列表怎么办？您需要跟踪是否找到了一个。因此，假设我们使用了索引和布尔国旗的元组。

您的功能将您传递给fold_left只需要确定如果发现匹配不需要更新。从本质上讲，我们只是在列表的其余部分中毫不费力。但是，如果我们还没有找到匹配项，那么我们需要测试当前的sublist的长度并相应地更新初始值。

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 the list. If the list is empty, it returns the initial value. Otherwise it uses the function to update the initial value by way of recursion and works on the 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.

回复收藏 0 原文

剧终人散尽 2025-02-14 21:36:13

@glennsl（在评论中）和@chris已经解释说您 May 使用list.fold_left，但它不是工作的正确工具，因为它处理了整个列表而发现发生后，您想停止。有解决方案，但它们并不令人满意：（

@chris的解决方案:)使用折叠功能，一旦发现发生，就会忽略新元素：您只是在浪费时间，在剩下的尾巴上走过一无所有；
通过抛出和捕获一个例外来逃避循环：更好但骇客，您正在围绕list.fold_left的正常功能进行工作。

我只是提到是标准库这几乎与您的处境相匹配：

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

查找f l返回列表的第一个元素l满足谓词f。
提高not_found如果在列表中没有满足f的值l。
。

但是，与您的要求不同，它不会返回索引。这是标准库中故意的设计选择，因为列表索引效率低下（线性时间），您不应该这样做。如果在这些警示单词之后，您仍然需要索引，则很容易编写通用函数find_with_index。

代码上的另一项说明：您可以避免根据以下标准功能来完全计算内部列表的长度：

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

将列表的长度与整数进行比较。 compare_length_with l len等效于compare（length l）len，只是该计算在列表上最多len迭代时停止。<
由于4.05.0

因此而不是如果list.length hd = x，则可以执行，如果list.compare_length_with hd hd x = 0。

@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, because it processes the whole list whereas you want to stop once an occurrence is found. There are solutions but they are not satisfying:

(@Chris’ solution:) use a folding function that ignores the new elements once an occurrence has been found: you’re just wasting time, walking through the remaining tail for nothing;
evade the loop by throwing and catching an exception: better but hacky, you’re working around the normal functioning of List.fold_left.

I 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 these 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.

回复收藏 0 原文

~没有更多了~