Lista de enlaces f#implementada con registros

linked-list

Question

Estoy tratando de implementar una lista enlazada en f # usando registros. Sé que puedo usar la compilación en el tipo de lista, pero esto es para fines de aprendizaje. Mi tipo es:

type Cell = { data : int; next : RList}
and RList = Cell option ref

Y me gustaría hacer una función de inserción simple, pero me dijeron que f # está esperando un booleano, pero se le dio una expresión de unidad de tipo. Me pregunto si esto significa que he formateado mi sentencia if / else incorrectamente

let rec insert comp (item: int) (list: RList) =
    let c = {data = item; next = ref None}
    match !list with
     | None -> list = cellToRList c
     | Some {data = d; next = remaining} -> 
        if (comp(item, d)) then
            c.next := !remaining
            remaining := ref c (* compiler indicates error here *)
        else insert comp item remaining

Nota: comp es cualquier función de comparación tomando (elemento, d) como entrada y dando salida a verdadero o falso ex:

let compare (x, y) = x > y

Mi objetivo es simplemente insertar una nueva celda con datos = ítem si comparo salidas verdaderas. En el ejemplo anterior, podría usarse para insertar en una lista ordenada y mantener la ordenación. Toda la función debería devolver la unidad de tipo. Cualquier sugerencia sobre por qué mi intérprete está buscando un booleano sería muy apreciado.

Nota: soy muy nuevo en F #

====

Corregido con mejoras Cortesía de Foggy, Mikhail y Fyodor

type Cell = { data : int; next : (Cell option) ref}

let rec insert compare (item: int) (list: (Cell option) ref) : unit =
    let c = {data = item; next = ref None}
    match !list with
    | None -> list := Some c
    | Some {data = d; next = remaining} -> 
        if (compare(d, item)) then
            c.next := !remaining
            remaining := Some c
        else insert compare item remaining

Answer 1

Usted devuelve un bool de su coincidencia de None :

| None -> list = cellToRList c

El signo de igual es un operador de comparación aquí. Entonces el compilador deduce la función para devolver bool , mientras que supongo que tu intención es devolver la unit .

En cualquier caso, siempre que no comprenda los tipos inferidos de sus funciones, intente anotarlos explícitamente. En tu caso, hazlo

let rec insert comp (item: int) (list: RList) : unit =

Y verás el problema que describí arriba.

Es posible que desee eliminar la anotación de tipo una vez que todo se compila.