Складывание списка в OCaml - PullRequest
Новая
       49

Складывание списка в OCaml

0 голосов
/ 25 сентября 2018

В OCaml типичная функция сгиба выглядит следующим образом: 

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

Для тех, кто знаком с OCaml (в отличие от меня), все должно быть довольно просто.

I 'm написание функции, которая возвращает true, когда все элементы в списке удовлетворяют условию: если условие x истинно для всех x в некотором списке l.Однако я реализую функцию, используя функцию сгиба, и я застрял.В частности, я не знаю, что список должен вернуть.Я знаю, что в идеале условие должно применяться к каждому элементу в списке, но я понятия не имею, как должен выглядеть синтаксис.x && acc работает, но не проходит очень простой тест (показано ниже) 

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

Вот моя предварительная попытка.Любая помощь приветствуется: 

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

1 Ответ

0 голосов
/ 25 сентября 2018 
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

Ваша функция объединения не должна делать x && base, потому что элементы списка обычно не bool.Вы хотите, чтобы ваша предикатная функция сначала оценивала элемент как bool, а затем "и" его с помощью аккумулятора.

Нет необходимости в begin и end в fold.Вы можете просто сопоставить с шаблоном match <identifier> with.

. Существует два распространенных типа fold: fold_left и fold_right.Вы используете fold_right, который, по сути, проходит через весь список и начинает «комбинировать» с конца списка на передний план.Это не хвост-рекурсив .

fold_left, с другой стороны, идет впереди списка и сразу объединяет каждый элемент с аккумулятором.Это не «съедает» ваш стек рядом рекурсивных вызовов функций.

...