F # Split Function

Question

Sto costruendo una funzione di merge sort e il mio metodo split mi dà un errore di restrizione del valore. Sto usando 2 parametri di accumulo, i 2 elenchi risultanti dalla divisione, che impacchetta in una tupla alla fine per il ritorno. Tuttavia sto ricevendo un errore di restrizione del valore e non riesco a capire quale sia il problema. Qualcuno ha qualche idea?

let split lst = 
    let a = [] 
    let b = [] 
    let ctr = 0 
    let rec helper (lst,l1,l2,ctr) = 
     match lst with 
      | [] -> [] 
      | x::xs -> if ctr%2 = 0 then helper(xs, x::l1, l2, ctr+1) 
        else 
        helper(xs, l1, x::l2, ctr+1) 
    helper (lst, a, b, ctr) 
    (a,b) 

Qualsiasi input è apprezzato.

Answer 1

Il codice, come è stato scritto, non ha molto senso. F # usa valori immutabili per impostazione predefinita, quindi la funzione, come è attualmente scritto, può essere semplificata a questo:

let split lst = 
    let a = [] 
    let b = [] 
    (a,b) 

Questo non è probabilmente quello che volete. In effetti, a causa di legami immutabili, non c'è alcun valore nel predecare a, b e ctr.

Ecco una funzione ricorsiva che farà il trucco:

let split lst = 
    let rec helper lst l1 l2 ctr = 
     match lst with 
     | [] -> l1, l2 // return accumulated lists 
     | x::xs -> 
      if ctr%2 = 0 then 
       helper xs (x::l1) l2 (ctr+1) // prepend x to list 1 and increment 
      else 
       helper xs l1 (x::l2) (ctr+1) // prepend x to list 2 and increment 
    helper lst [] [] 0 

Invece di utilizzare una funzione ricorsiva, si potrebbe anche risolvere questo problema utilizzando List.fold, fold è una funzione di ordine superiore, che generalizza il processo di accumulazione che abbiamo descritto esplicitamente nella funzione ricorsiva di cui sopra.

Questo approccio è un po 'più conciso, ma molto probabilmente meno familiare per chi è nuovo alla programmazione funzionale, quindi ho cercato di descrivere questo processo in modo più dettagliato.

let split2 lst = 
    /// Take a running total of each list and a index*value and return a new 
    /// pair of lists with the supplied value prepended to the correct list 
    let splitFolder (l1, l2) (i, x) = 
     match i % 2 = 0 with 
     |true -> x :: l1, l2 // return list 1 with x prepended and list2 
     |false -> l1, x :: l2 // return list 1 and list 2 with x prepended 
    lst 
    |> List.mapi (fun i x -> i, x) // map list of values to list of index*values 
    |> List.fold (splitFolder) ([],[]) // fold over the list using the splitFolder function