OCaml 分割函数

Question

我目前正在准备 CS 考试，我很难理解书中的练习。练习如下：

Define, using FOLDR and without using explicit recursion, a function (split : ’a list -> ’a -> ’a list * ’a list) such that split l n returns a pair of lists. The first contains all the values preceding the first occurrence of n in l (in the same order), and the second contains all the remaining elements (in the same order). If n does not appear in l, there are no values preceding the first occurrence of n.

示例：split [3;-5;1;0;1;-8;0;3] 0 = ([3;-5;1],[0;1;-8;0;3])、split [3;4;5] 7 = ([],[3;4;5])

这是我的教授为解决练习而编写的代码：

let split l n =
  let f x (l1, l2, b) =
    if x = n then ([], x::(l1@l2), true)
    else if b then (x::l1, l2, b)
    else (l1, x::l2, b)
  in let (l1, l2, b) = foldr f ([], [], false) l in (l1, l2) ;;

我完全不明白第二行(let f x (l1, l2, b))。

这些参数如何填充一个值，以便它附带的所有逻辑都有意义？例如：什么是x，如果没有值怎么和n比较？ b中那些布尔值是什么意思？

此外，我不明白最后一行中的 foldr 函数，而且我没有找到任何关于它的文档。事实上，甚至我的编译器也不理解 foldr 是什么，并给我一个错误 (*Unbound value foldr*)。最初我认为这是 List.fold_right 的某种缩写，但如果我尝试用后者替换，我仍然会收到错误消息，因为以下参数不正确 (

File "split.ml", line 6、字符41-56：
错误：此表达式的类型为 'a * 'b * 'c
       但表达式应为 'd list

).

类型

提前感谢您的帮助或建议。

Answer 1

这里是 CS 专业的同学。

let f x (l1, l2, b)

定义了一个函数，它有两个参数，一个叫做 x，另一个是 3 个参数的三元组 (l1, l2, b)。此函数的范围仅限于以下行

in let (l1, l2, b) = foldr f ([], [], false) l in (l1, l2) ;;

您可能遇到困难的部分是关键字 "in"，它将一个表达式的范围限制为下一个表达式。所以 exp2 中的 exp1 将表达式一的范围限制为表达式二。

另外，x和(l1,l2,b)代表任意参数，只在函数体内有效。查看 foldr 采用哪些参数（第一个应该是一个函数，它与您的教授定义的函数 f 具有相同的参数）。这个 foldr 函数然后在 foldr 的上下文中为 x（和（l1，l2，b））赋值。

let f x (l1, l2, b) 
....
in let (l1, l2, b) = foldr f ([], [], false) l in (l1, l2) ;;

虽然第一行中的 (l1, l2, b) 与第三行中的 (l1, l2, b) 不同（上面的代码片段），这里

in let (l1, l2, b) = foldr f ([], [], false) l in (l1, l2) ;;

l1 和 l2 相同（在 let (l1, l2, b) 和 (l1, l2) 中）。

PS: 你需要定义 foldr 函数（要么导入它，要么你的教授对练习 sheet 有一些定义，你可以复制）。

Answer 2

如果您使用 List.fold_right 那么这将有效。

let split l n =
  let f x (l1, l2, b) =
    if x = n
    then
      ([], x::(l1@l2), true)
    else if b
    then
      (x::l1, l2, b)
    else
      (l1, x::l2, b)
  in let (l1, l2, b) = List.fold_right f l ([], [], false)
  in (l1, l2)

Answer 3

我不知道OCAML的语法规则是否允许这样做，但是让我们添加一些额外的白色space以使其更清楚：

let split l n =
  let f x                      (   l1,        l2 , b    ) =
    if       x = n  then       (   [], x::(l1@l2), true )
    else if  b      then       (x::l1,        l2 , b    )  (* b is true  *)
    else                       (   l1, x::    l2 , b    )  (* b is false *)
  in let (l1, l2, b) = foldr f (   [],        [] , false)  l 
     in  (l1, l2) ;;

foldr 在伪代码中是

foldr f z [x1  ;   x2  ;  ...   ;   xn1  ;   xn             ]
 =
           x1 -f- (x2 -f- (... -f- (xn1 -f- (xn -f- z))...))

其中a -f- b表示简单应用f a b，为了方便写了中缀。也就是说，

foldr f z [x1 ;            x2 ; ... ; xn1 ; xn]     (*  x_{n-1}  *)
 =
      f    x1  (foldr f z [x2 ; ... ; xn1 ; xn])    (*  x_{n-1}  *)

而

foldr f z []  =  z

因此上面实际上等同于

 =  let    t1  = f xn  z
    in let t2  = f xn1 t1          (*  x_{n-1}  *)
    in ....
    in let tn1 = f x2  tn2         (*  t_{n-2}  *)
    in let tn  = f x1  tn1         (*  t_{n-1}  *)
    in     tn

您现在应该能够看到它所做的是从右到左处理列表的元素，将中间结果传递给左侧 f 的后续应用程序。

您现在应该也可以自己编写缺少的 foldr 定义了。

因此，如果我们替换您对 f 的特定定义，它是如何适用于列表的，例如三个元素 [x1; x2; x3] 其中 x2 = n，等同于

     let    (l1,   l2,   b  ) = (    [],             []    , false)
     in let (l1_3, l2_3, b_3) = (    l1,         x3::l2    , b    )
     in let (l1_2, l2_2, b_2) = (    [],   x2::(l1_3@l2_3) , true )
     in let (l1_1, l2_1, b_1) = (x1::l1_2,           l2_2  , b_2  )
     in     (l1_1, l2_1)

即

     let    (l1,   l2,   b  ) = (    [],               []  , false)
     in let (l1_3, l2_3, b_3) = (    [],           x3::[]  , false)
     in let (l1_2, l2_2, b_2) = (    [],  x2::([]@[x3])    , true )
     in let (l1_1, l2_1, b_1) = (x1::[], [x2 ;     x3]     , true )
     in     ([x1], [x2; x3])

因此生成的列表是从后面构建的。

传递的布尔标志允许函数正确处理列表中有多个元素等于 n 的情况。没有任何标志也可以实现相同的效果，而是使用一个小的 post-processing 步骤，如

let split l n =
  let f x           (   l1,        l2 ) =
     if x = n then  (   [], x::(l1@l2))
              else  (x::l1,        l2 )
  in match  foldr f (   [],        [] ) l  with
     | (l1, []) -> ([], l1) 
     | (l1, l2) -> (l1, l2) ;;

（如果这不是有效的 OCaml 代码，则将其作为伪代码）。

OCaml 分割函数

OCaml split function

ocaml

split

list

fold