Добавление элементов в списке слева OCaml

Question

Я написал функцию:

let rec addAll f l = 
    match l with 
    | [] -> 0 
    | [x] -> x 
    | hd::tl -> let combined = addAll f tl in 
       f (hd) combined 
;; 

I работает как с названием, он будет добавлять все элементы списка. Однако я хочу написать эту программу, так что она левая ассоциативная, поэтому вместо объединения элементов [1; 2; 3] в качестве 1 - (2 - 3), я хочу, чтобы это было: (1 - 2) - 3.

Любые намеки на то, как я могу сделать это вперед рекурсивным, а не хвостом? Или как я могу это сделать, чтобы эта функция работала так, как я предполагаю? Я знаю, что могу просто отменить список, но я хочу попробовать другой путь.

Answer 1

let rec addAll f l = 
    match l with 
    | []  -> 0 
    | [x]  -> x 
    | x::y::tl -> addAll f ((f x y)::tl) 
;; 

Тест

# addAll (fun a b -> Printf.printf "(%d %d)" a b; a+b) [1;2;3];; 
(1 2)(3 3)- : int = 6 

Answer 2

Ваш код делает правильную складку. Грубо говоря, это примерно так:

let addAll f l = List.fold_right f l 0 

Вы хотите сменить его на левую складку. Грубо говоря, вы хотите:

let addAll f l = List.fold_left f 0 l 

Или, чуть более точно вы хотите:

let addAll f = function 
| [] -> 0 
| h :: t -> List.fold_left f h t 

Эта вторая функция не кажется, делать то, что вы хотите:

# addAll (-) [1;2;3];; 
- : int = -4 

Если вы хотите напишите его с нуля (не используя List.fold_left), самый простой способ - с аккумулятором:

let addAllScratch f l = 
    let rec iadd f accum l = 
     match l with 
     | [] -> accum 
     | a::l -> iadd f (f accum a) l 
    in 
    match l with 
    | [] -> 0 
    | h :: t -> iadd f h t 

Это делать то, что вы хотите:

# addAllScratch (-) [1;2;3];; 
- : int = -4 

(В сущности, я просто вставил стандартное определение List.fold_left в код.)