Pages: [1]   Go Down
Print
Author Topic: Merge Sort in Scheme (II)  (Read 1658 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
ossacolsale
Matricola
*
Offline Offline

Posts: 23


« on: 26-03-2012, 14:12:23 »

Vediamo se sto iniziando ad imparare la lezione sulla ricorsione (anche se c'è da dire che il Merge Sort mi pare già di suo essenzialmente/strutturalmente ricorsivo).

Di seguito è la mia versione per la quale ho perso le solite due ore, di cui un'ora e tre quarti per sistemare la sintassi (!!!) e un quarto d'ora per definire le funzioni:

(define (mergesort ls)
  (if (or (null? ls) (null? (cdr ls)))
      ls
      (merge (mergesort (partizione ls (length ls) #t))
             (mergesort (partizione ls (length ls) #f)) empty)))

(define (partizione ls len i?) ;i? -> booleano, prima meta'? altrimenti seconda meta'
  (if (> (ceiling (/ len 2)) (- len (length ls)))
      (if i?
          (cons (car ls) (partizione (cdr ls) len i?))
          (partizione (cdr ls) len i?)
      )
      (if i? '() ls)))

(define (merge ls1 ls2 ml)
  (cond ((null? ls1)
      (append ml ls2))
      ((null? ls2)
      (append ml ls1))
      ((< (car ls1) (car ls2))
       (merge (cdr ls1) ls2 (append ml (list (car ls1)))))
      (else (merge ls1 (cdr ls2) (append ml (list (car ls2)))))))

E' abbastanza ricorsivo? Si può fare in un altro modo?

Saluti.
gm
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.079



WWW
« Reply #1 on: 26-03-2012, 17:42:54 »

(define (partizione ls len i?) ;i? -> booleano, prima meta'? altrimenti seconda meta'
  (if (> (ceiling (/ len 2)) (- len (length ls)))
      (if i?
          (cons (car ls) (partizione (cdr ls) len i?))
          (partizione (cdr ls) len i?)
      )
      (if i? '() ls)))

Orrore!!!
Che e' 'sto booleano?!
Al limite fai due funzioni separate.

Quello di dividere in due una lista e' un procedimento che ricorsivamente
non viene cosi' semplice.
Se non vuoi proprio "dividerla" in due, ma avere due sottoliste composte dagli elementi della lista data
(cosa che in fondo e' cio' che ci serve, a meno di ottimizzazioni)
puoi fare

(define (divide ls)
  (cond ((null? ls)
                          (list empty empty))
            ((null? (cdr ls))
                           (list empty (list (car ls))))
             (else (let ((res (divide (cddr ls))))
                          (list (cons (car ls) (car res))
                                 (cons (cadr ls) (cadr res)))))))

divide restituisce una lista contenente le due sottoliste.
Occorre utilizzare l'espressione let, che permette di dare un nome locale ad un valore
all'interno di una espressione.
Nel nostro caso diamo nome res al risultato della chiamata ricorsiva  (divide (cddr ls))
ed utilizziamo res per fornire il risultato finale.
La stessa cosa si puo' fare in haskell in modo estramamente piu' compatto e leggibile,
come vedremo.

Salutoni
FB


« Last Edit: 26-03-2012, 17:58:11 by Franco Barbanera » Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.079



WWW
« Reply #2 on: 26-03-2012, 17:55:00 »

(define (merge ls1 ls2 ml)
  (cond ((null? ls1)
      (append ml ls2))
      ((null? ls2)
      (append ml ls1))
      ((< (car ls1) (car ls2))
       (merge (cdr ls1) ls2 (append ml (list (car ls1)))))
      (else (merge ls1 (cdr ls2) (append ml (list (car ls2)))))))

Anche qui, hai utilizzato la ricorsione di coda.
Infatti in questo modo tu usi ml come se fosse una variabile globale
che vai modificando durante un'iterazione.

Una possibile versione ricorsiva (migliorabile forse utilizzando il let)
e'
(define (merge ls1 ls2)
  (cond ((null? ls1)
            ls2)
        ((null? ls2)
            ls1)
        (else (append (if (< (car ls1) (car ls2))
                         (list (car ls1) (car ls2))
                         (list (car ls2) (car ls1)))
                      (merge (cdr ls1) (cdr ls2))))))

Per dubbi, e perplessita', domani a lezione.

Salutoni
FB
« Last Edit: 26-03-2012, 17:59:02 by Franco Barbanera » Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.079



WWW
« Reply #3 on: 26-03-2012, 17:56:54 »

Quote
di cui un'ora e tre quarti per sistemare la sintassi (!!!)

 

Tranquillo. Poi passiamo ad haskell.
« Last Edit: 26-03-2012, 17:58:49 by Franco Barbanera » Logged
ossacolsale
Matricola
*
Offline Offline

Posts: 23


« Reply #4 on: 26-03-2012, 18:18:36 »

Capito il meccanismo ho corretto la versione di merge che lei ha proposto (e che non funzionava per un piccolo errore interpretativo).

In questo modo invece funziona:

(define (merge ls1 ls2)
  (cond ((null? ls1)
            ls2)
        ((null? ls2)
            ls1)
        (else (if (< (car ls1) (car ls2))
                   (append (list (car ls1)) (merge (cdr ls1) ls2))
                   (append (list (car ls2)) (merge ls1 (cdr ls2)))))))

Grazie ancora.
gm
« Last Edit: 26-03-2012, 18:20:32 by ossacolsale » Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.079



WWW
« Reply #5 on: 27-03-2012, 10:22:07 »

Quote
la versione di merge che lei ha proposto (e che non funzionava per un piccolo errore interpretativo)

Che errore?
Quando l'ho provata su DrRacket funzionava...

FB
Logged
ossacolsale
Matricola
*
Offline Offline

Posts: 23


« Reply #6 on: 27-03-2012, 11:35:15 »

Mi sono espresso malissimo.
La sua versione di merge funzionava ma "non effettuava correttamente il merge".
Ad esempio tra le due liste [2 3] e [4 5] il risultato del merge sarebbe stato [2 4 3 5].

(ora purtroppo non posso fare una prova pratica perché sono a lavoro e non ho drracket, ma mi pare che fosse all'incirca come ho detto)

Saluti.
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.079



WWW
« Reply #7 on: 27-03-2012, 14:59:13 »

Mi sono espresso malissimo.
La sua versione di merge funzionava ma "non effettuava correttamente il merge".

E quindi NON funzionava.
Infatti non funziona.
La tua versione funziona, ma si puo' leggermente migliorare nel modo seguente

(define (merge ls1 ls2)
  (cond ((null? ls1)
            ls2)
        ((null? ls2)
            ls1)
        (else (if (< (car ls1) (car ls2))
                   (cons (car ls1) (merge (cdr ls1) ls2))
                   (cons (car ls2) (merge ls1 (cdr ls2)))))))

Salutoni
FB
Logged
ossacolsale
Matricola
*
Offline Offline

Posts: 23


« Reply #8 on: 27-03-2012, 18:43:46 »

Mi sono espresso malissimo.
La sua versione di merge funzionava ma "non effettuava correttamente il merge".

E quindi NON funzionava.
Chi, come me, si esprime malissimo lo fa ricorsivamente.

Questo concetto che ho espresso, se è chiaro, è il caso base della ricorsione.

 

Saluti.
gm
« Last Edit: 27-03-2012, 19:27:18 by ossacolsale » Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #9 on: 27-03-2012, 20:15:15 »

io generalizzerei cosi' la funzione

(define (merge ls1 ls2 prec?)
  (cond
    ((null? ls1) ls2)
    ((null? ls2) ls1)
    ((prec? (car ls1) (car ls2)) (cons (car ls1) (merge (cdr ls1) ls2 prec?)))
    (else (cons (car ls2) (merge ls1 (cdr ls2) prec?)))))

 

P.s. a me piacciono piu' lisp e scheme che haskell... ma sara' questione di gusti ^^
« Last Edit: 27-03-2012, 22:58:45 by shiny » Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.079



WWW
« Reply #10 on: 28-03-2012, 10:19:00 »

io generalizzerei cosi' la funzione

(define (merge ls1 ls2 prec?)
  (cond
    ((null? ls1) ls2)
    ((null? ls2) ls1)
    ((prec? (car ls1) (car ls2)) (cons (car ls1) (merge (cdr ls1) ls2 prec?)))
    (else (cons (car ls2) (merge ls1 (cdr ls2) prec?)))))

Giusta osservazione.
Quote
P.s. a me piacciono piu' lisp e scheme che haskell... ma sara' questione di gusti ^^

Non trovo l'emoticon "faccina schifata"....
 

Logged
Pages: [1]   Go Up
Print
Jump to: