recursion - F#Función dividida

split value-restriction

Question

Estoy construyendo una función de clasificación de fusión y mi método de división me está dando un error de restricción de valor. Estoy usando 2 parámetros de acumulación, las 2 listas resultantes de la división, que empaqueto en una tupla al final para la devolución. Sin embargo, recibo un error de restricción de valor y no puedo entender cuál es el problema. ¿Alguien tiene alguna 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)

Cualquier entrada es apreciada.

Answer 1

El código, como lo has escrito, realmente no tiene sentido. F # usa valores inmutables por defecto, por lo tanto, su función, tal como está escrita actualmente, se puede simplificar a esto:

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

Esto probablemente no es lo que quieres. De hecho, debido a enlaces inmutables, no hay ningún valor en predeclar a, b y ctr .

Aquí hay una función recursiva que hará el truco:

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

En lugar de usar una función recursiva, también podría resolver este problema usando List.fold , fold es una función de orden superior que generaliza el proceso de acumulación que describimos explícitamente en la función recursiva anterior.

Este enfoque es un poco más conciso pero muy probablemente menos familiar para alguien nuevo en la programación funcional, así que traté de describir este proceso con más detalle.

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