Функция разделения OCaml

Question

В настоящее время я готовлюсь к экзамену CS, и мне трудно понять упражнение из моей книги. Упражнение выглядит следующим образом:

Определите, используя FOLDR и без использования явной рекурсии, функцию (split : ’a list -> ’a -> ’a list * ’a list) такую, что split l n возвращает пару списков. Первый содержит все значения, предшествующие первому вхождению n в l (в том же порядке), а второй содержит все оставшиеся элементы (в том же порядке ). Если n не отображается в l, отсутствуют значения, предшествующие первому вхождению 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)).

Как эти параметры заполняются значением, так что все логики c, которые идут с ним имеет смысл? Например: что такое x и как его можно сравнить с n, если оно не имеет значения? Что означают эти логические значения в b?

Кроме того, я не понимаю, что foldr работает в последней строке, и я не нахожу никакой документации по этому поводу. На самом деле, даже мой компилятор не понимает, что такое foldr, и выдает ошибку (*Unbound value foldr*). Первоначально я думал, что это было какое-то сокращение для List.fold_right, но если я пытаюсь заменить его на последнее, я все равно получаю сообщение об ошибке, поскольку следующие параметры не верны (

File "split.ml", line 6, characters 41-56:
Error: This expression has type 'a * 'b * 'c
       but an expression was expected of type 'd list

).

Заранее спасибо за любую помощь или совет.

Answer 1

Если вы используете 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 2

Я не знаю, разрешено ли это правилами синтаксиса OCAML или нет, но давайте добавим немного дополнительного пробела, чтобы сделать его более понятным:

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 самостоятельно.

---

Так что, если мы подставим указанное вами c определение 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. Тот же эффект может быть достигнут без каких-либо флагов, с небольшим шагом последующей обработки, например

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, тогда примите его как псевдокод).

Answer 3

Товарищ майор CS здесь.

let f x (l1, l2, b) 

определяет функцию, которая принимает два аргумента, один из которых называется x, а третий представляет собой тройку из трех аргументов (l1, l2, b). Область действия этой функции ограничена следующей строкой

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

Часть, с которой вы, вероятно, боретесь, - это ключевое слово "in", которое ограничивает область действия одного выражения следующим. поэтому exp1 в exp2 ограничивает область действия выражения один до выражения два.

Кроме того, x и (l1, l2, b) обозначают произвольные параметры, допустимые только в теле функции. Посмотрите, какие параметры принимает foldr (первая должна быть функцией, которая имеет те же параметры, что и функция, определенная вашим профессором). Эта функция foldr затем присваивает значение x (и (l1, l2, b)) в контексте foldr.

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 (либо импортируйте ее, либо, возможно, у вашего профессора есть какое-то определение в листе упражнений, которое вы можете скопировать).