Усечение списка в OCaml

Question

Возможно ли усечь список после заданного элемента в OCaml без использования рекурсии?

let truncate (elt: 'a) (q: 'a queue) : unit = 

я могу думать о потенциально, как это сделать с помощью вложенного шаблона соответствие ... ищет лучший способ без геи

Answer 1

Перечня узлов содержит все следующие элементы.

Следовательно, чтобы усечь список, вам нужно создать новый список, содержащий только первые элементы (это единственный способ получить нужный усеченный список).

Таким образом, тип функции, которую вы ищете

let truncate : 'a -> 'a list -> 'a list 
= fun elt queue -> ... 

Как говорит Джеффри Скофилд, нет никакого смысла избежать рекурсии.

Answer 2

Несомненно, если вы действительно хотите, вы можете сделать много вещей. Есть два примера технического избегания рекурсии, и тогда то, что я думаю, что вы, возможно, уже на самом деле искали:

let truncate1 elt list = (* tedious iteration version *) 
    let list = ref list in 
    let r = ref [] in 
    while !list <> [] do 
    r := List.hd !list :: !r; 
    if List.hd !list = elt then list := [] else 
     list := List.tl !list 
    done; 
    List.rev !r 

let truncate2 elt list = (* let's not mind how List.find does it version *) 
    let r = ref [] in 
    ignore (List.find (fun x -> r := x :: !r; x = elt) list); 
    List.rev !r 

(* this is more what you're looking for? version *) 
type 'a mutcons = { mutable head : 'a; mutable tail : 'a mutlist } 
and 'a mutlist = Nil | Cons of 'a mutcons 

let rec mutlist_iter f = function 
    | Nil ->() 
    | Cons k -> f k; mutlist_iter f k.tail 

let rec truncate3 elt mlist = 
    mutlist_iter (fun k -> if k.head = elt then k.tail <- Nil) mlist 

Если последние подходит изменяемый список и мутирует текущую ячейку последний из списка если он содержит данный элемент.

Answer 3

То, что вы описываете, является деструктивной структурой данных, поэтому с изменяемыми значениями и некоторое время вы можете это сделать.

Интерфейс очереди является хорошим. Поп-значения до тех пор, пока вы не найдете элемент желания:

Pseudo alorithm 
Do 
    Current = queue.pop myqueue 
Until (current = desiredvalue) or (queue.isempty myqueue) 

Return myqueue