Así que tengo que eliminar el último elemento de una lista en el esquema.eliminando el último elemento de una lista (esquema)
Por ejemplo, digamos que tengo una lista (1 2 3 4). Tengo que devolver:
(1 2 3)
Mi idea:
reverse(list)
car(list)
reverse(list)
¿Hay una función en el esquema reverse (raqueta)?
Haría una función recursiva que aparece en la lista y adjunta el elemento (usando cons) si el elemento que está detrás no es el último, y no añade nada si no lo está.
No he hecho el esquema durante años, así que eso es todo lo que puedo.
Alguien puede funcionar con la forma de ponerla en práctica (a menos que sea la tarea, entonces probablemente no debería!)
-1 Agregar una lista es una operación O (n) cada vez, lo que hace que toda su función sea O (n²). Eso es lo que obtienes cuando trabajas con listas enlazadas. –
Adjuntar a una lista en no es O (n). Anexar a una lista respaldada por una matriz es O (n). Anexar a una lista vinculada (como en el esquema) es O (1). – corsiKa
@glowcoder: No es cierto. _Prepending_ a una lista vinculada es O (1). _Aparece_ a una lista vinculada es O (n) en la lista que se adjunta. (Recuerde, las listas de Scheme son listas de enlace único, no doblemente vinculadas). –
Usted escribió: "marcha atrás, coche, marcha atrás". Creo que quisiste escribir "reverse, cdr, reverse". No hay nada malo con esta solución; es lineal en el tamaño de la lista, al igual que cualquier solución a esto que use las listas estándar.
Como código:
;; all-but-last: return the list, not including the last element
;; list? -> list?
(define (all-but-last l) (reverse (cdr (reverse l))))
Si el recorrido múltiple de la lista o la construcción innecesaria de otra copia lista le molesta, que sin duda puede evitarlo, escribiendo directamente la cosa.
Dada tu casi solución, voy a suponer que esto no es tarea.
Esto es lo que se vería así, en la raqueta:
#lang racket
(require rackunit)
;; all-but-last : return the list, except for the last element
;; non-empty-list? -> list?
(define (all-but-last l)
(cond [(empty? l) (error 'all-but-last "empty list")]
[(empty? (rest l)) empty]
[else (cons (first l) (all-but-last (rest l)))]))
(check-equal? (all-but-last '(3 4 5))
'(3 4))
p.s .: esta solución usa varios ismos de racket: primero & rest, error, check-equal ?, etc. Supongo que está bien, porque su pregunta está etiquetada como "racket". –
SRFI 1 (activar en la raqueta usando (require srfi/1)) tiene una función drop-right:
(drop-right '(1 2 3 4) 1) ; => (1 2 3)
Hay una reverse, pero utilizando Sería no ser muy eficiente Sugiero la siguiente función recursiva.
(define (remove-last lst)
(if (null? (cdr lst))
'()
(cons (car lst) (remove-last (cdr lst)))))
(remove-last '(1 2 3 4)) ; returns '(1 2 3)
Los if comprueba si está en el último elemento de la lista.
En realidad, 'reverse' es O (n), al igual que su función. Ambos enfoques están bien. –
@Chris: en realidad son de la misma clase de complejidad, pero este algoritmo debería ser el doble de rápido porque solo cruza la lista una vez. – Tim
Solo si usa una definición muy estrecha de "poligonal". Dado que su función no es recursiva de la cola, el proceso de conserjería de su pila de llamadas podría verse como el segundo recorrido. –
Escribiría una recursión simple, alterando el típico caso base "empty? Mylist" a "empty? (Rest mylist)", para que pueda volver vacío cuando la lista de entrada es solo 1 elemento.
(define (removelast mylist)
(cond
[(empty? (rest mylist)) empty]
[(cons? mylist) (cons (first mylist) (removelast (rest mylist)))]))
(removelast (list 1 2 3 4 5))
Dicho sea de paso, este código está en Racket/PLT Scheme, un subconjunto de Scheme.
que he hecho algo más simple que: reverse (lista), coche (lista), atrás (lista) para obtener el último elemento, echa un vistazo a:
(define (last-one liste)
(if(null? (cdr liste))
null
(cons (car liste) (last-one (cdr liste)))
)
)
De hecho, una de las mejores cosas de Stackoverflow es que una vez que se publica una pregunta, se puede referenciar y desarrollar en otras publicaciones.SO es uno de los principales éxitos en Google cuando buscas cosas, por lo que si alguien se encuentra con esto en el futuro, puede aprender de lo que está aquí. :) – corsiKa
Para saber si Racket tiene una función inversa, use docs.racket-lang.org para buscarla. – soegaard