Programare functionala [Scheme]

[actunderdc]

Buna ziua tuturor,

Am un proiect de facut in Scheme dar sunt incepator in acest limbaj, iar la unele chestii nu gasesc raspunsul pe google (cel putin nu suficient de repede). As dori sa mai pun cateva intrebari pe parcurs, daca este cineva care se pricepe bine si poate sa imi dea un raspuns mi-ar fi de mare folos.

Pentru inceput, m-am blocat aici:

Am o lista de liste de caractere:

(define ls '( '(#\c #\d #\d) '(#\a #\c #\s) '(#\d #\s #\k) '(#\c #\b #\a)))

Si am nevoie sa sortez aceasta lista lexicografic (dupa primul caracter din fiecare lista, daca sunt egale dupa al doilea, s.a.m.d).

Outputul ar trebui sa arate (sub forma unei noi liste) :

'('(#\a #\c #\s) '(#\c #\b #\a) '(#\c #\d #\d) '(#\d #\s #\k))

Functia sort nu functioneaza (pentru ca are nevoie ca elementele listei sa fie numere, in cazul meu sunt liste)

Multumesc anticipat!

[M2G]

Nu stiu programare funtionala pentru ca nu am facut inca la faculta dar cred ca iti pot da o idee. Daca zici ca sort functioneaza doar cu numere ai putea sa transformi caracterele in coduri ascii si apoi sa le sortezi. Dupa sortare faci conversia din codurile ascii inapoi in caractere. Doar o idee, hope it helps.

[em]

Prea multe quoturi. Functia de care a zis M2G. Acum foloseste sort.

(define ls '( (#\c #\d #\d) (#\a #\c #\s) (#\d #\s #\k) (#\c #\b #\a)))

(define convert
  (?(x) 
    (if (null? x)
        '()
        (append (list (cons (char->integer (first (car x))) (cons (char->integer (second (car x))) (cons (char->integer (third (car x))) '())))) (convert (cdr x))))))

Sau direct asa

(define ls '( (#\c #\d #\d) (#\a #\c #\s) (#\d #\s #\k) (#\c #\b #\a)))
(define maimic
  (?(x y)
    (if (null? x) 
        #f
        (if (eq? (car x) (car y))
             (maimic (cdr x) (cdr y))
             (if (char<? (car x) (car y))
                  #t
                  #f)))))
(sort ls maimic)

Output:

((#\a #\c #\s) (#\c #\b #\a) (#\c #\d #\d) (#\d #\s #\k))

E la fel ca in java, trebuie sa ii dai argument un comparator.

[actunderdc]

Multumesc foarte mult em, solutia ta cu recursivitate este foarte buna si functioneaza. +1 rep

Voi mai reveni in acest topic cu eventuale probleme/intrebari.

[actunderdc]

In continuare:

(define ls '( (#\c #\d #\d) (#\a #\c #\s) (#\d #\s #\k) (#\c #\b #\a)))

Si imi doresc din aceasta lista de liste sa creez o noua lista care contine doar ultimul element din fiecare lista, adica noua lista sa fie:

'( #\d #\s #\k #\a).

Codul implementat de mine:

(define extract

(lambda (x y)

(define aux1 (car x)) ; extrag prima lista

(define aux2 (reverse aux1)) ; inversez prima lista

(define aux3 (cons (car aux2) y)) ; pun primul elem din lista inversata in y

(if (null? x)

#f

(extract (cdr x) y)) ; reapelez functia pt a trece la urmatoarea lista din lista

#t))

La apelul:

(extract ls '())

primesc eroare: car: expects argument of type <pair>; given ()

Unde gresesc? Observ ca daca comentez if-ul, totul merge ok, deci undeva in recursivitate se buseste ceva

[em]

Încearc? s? gânde?ti totul recursiv. Asta e ideea acestei paradigme.

(define ls '( (#\c #\d #\d) (#\a #\c #\s) (#\d #\s #\k) (#\c #\b #\a)))
(define ultimele
  (?(x)
    (if (null? x) '()
        (cons (cddar x) (ultimele (cdr x))))))
(ultimele ls)

> ((#\d) (#\s) (#\k) (#\a))

LE: Acum am vazut ca de fapt iti returneaza o lista de liste. No prob. Mai aplici inca un car cddar-ului.

[actunderdc]

Recursiv recursiv, dar faza cu cddar merge doar daca listele din lista au 3 elemente, nu si pe o lungime diferita. De aceea eu ma gandeam sa inversez fiecare lista si sa iau car de pe fiecare.

[em]

(define ls '( (#\c #\d #\d) (#\a #\c #\s) (#\d #\s #\k) (#\c #\b #\a)))
(define ultimele
  (?(x)
    (if (null? x) '()
        (cons (car (reverse (car x))) (ultimele (cdr x))))))
(ultimele ls)

[actunderdc]

Thank you!

Cat de simpla era solutia si cat de mult ma complicam eu (cu declarari suplimentare de liste)

[actunderdc]

Ma intereseaza daca exista in Scheme o functie care sa imi intoarca indexul unui caracter dintr-un string. (se presupune ca nu se repeta caracterele in string).

De exemplu:

(define s "AbcaeNmR")

Iar functia pos (asa sa o botezam):

(pos s #\

sa intoarca 1 sau 2 (depinde daca numerotarea incepe de la 0 sau 1)

Pe net ( MIT Scheme Reference - Strings ) am gasit functia string-find-next-char , dar la un apel :

(string-find-next-char "Adam" #\A)

Primesc eroarea:

reference to undefined identifier: string-find-next-char

[em]

(define aparitii
  (?(string caracter)
    (if (= 0 (string-length string)) -1337
        (if (eq? (car (string->list string)) caracter) 0
            (+ 1 (aparitii (list->string (cdr (string->list string))) caracter))))))

> (aparitii "Geosu" #\e)
1
> (aparitii "Geosu" #\g)
-1332
> (aparitii "Geosu" #\G)
0
> 

Da numar negativ in caz de nu gaseste. Dac? ai înv??at call/cc î?i pot face s? returneze -1 mereu când nu g?se?te, am zis s? nu complic.

[actunderdc]

Exact ce aveam nevoie! Ma asteptam totusi scheme sa aiba ceva predefinit dar se pare ca degeaba cautam asa ceva. Multumesc

[actunderdc]

Acum imi bat capul rau cu o functie care imi da raspuns eronat.

Se da o lista/vector (sa luam '(5 3 2 1)) si un numar (de exemplu 7). Codul C pt ceea ce vreau sa fac este:

result="1"
for i in l:             
    if n >= l[i]:                 
         n = n - l[i]                 
         result = "1" + result             
    else 
         result = "0" + result     
return result

In urma evaluarii se obtine : 01011

Acum incerc sa fac acest lucru in Scheme:

(define result "1")
(define fibo_encode
  (lambda (x l)
      (if (null? l)
          result
      (if (>= x (car l))
          (begin (set! x (- x (car l))) (string-append "1" result)  (fibo_encode x (cdr l)))
      (begin (string-append "0" result)  (fibo_encode x (cdr l)))))))

Si apelez:

(fibo_encode 7 '(5 3 2 1))

Dar la output obtin doar "1". Din cate am observat (null? l) il evalueaza eronat. Ce imi scapa?

[em]

(define fibo_encode_temp
  (lambda (x l)
      (if (null? l)
          ""
      (if (or (null? l) (>= x (car l)))
          (string-append (fibo_encode_temp (- x (car l)) (cdr l)) "1" )
          (string-append (fibo_encode_temp x (cdr l)) "0" )))))

(define fibo_encode
  (lambda (x l)
    (string-append (fibo_encode_temp x l) "1")))

(fibo_encode 7 '(5 3 2 1))

F?r? seturi. Chiar sunt curios cum a? putea face recursivitatea aia intr-o singur? func?ie.

[actunderdc]

A functionat, multumesc.

Acum am asa. Se da o lista de 0 si 1:

(define l '(0 0 1 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 1))

Si doresc spargerea ei intr-o lista de liste la intalnirea a doua aparitii de "1" consecutiv:

'( (0 0 1 1) (1 0 1 1) (1 0 1 1) (1 0 0 1 1) (1 1) (0 1 0 1 1) (0 1 0 1 1) ( 0 0 0 1 1) (1 1) (0 1 1) (0 0 1 1) (1 0 1 1) )

Iar apoi (eventual si mai putin imporant) ultimul 1 trebuie scos dn fiecare lista) :

'( (0 0 1) (1 0 1) (1 0 1) (1 0 0 1) (1) (0 1 0 1) (0 1 0 1) ( 0 0 0 1) (1) (0 1) (0 0 1) (1 0 1) )

Codul incercat de mine imi scoate doar prima lista, apoi se opreste. Nu stiu cum sa folosesc recursivitatea sa mearga pana la final

(define l '(0 0 1 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 1))

(define q '())

(define break
  (lambda (l p)
    (if (eq? 1 (* (car l) (cadr l)))
     (cons (reverse (cons 1 p)) q)
    (begin (cons(car l)p ) (break(cdr l)(cons (car l) p) )
    )
     )
    ))

(break l '())

Output:

((0 0 1))

[em]

Rezolvarea

(define l '(0 0 1 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 1))
(define sparge
  (?(list)
    (if (or (null? list) (= 1 (length list))) '()
        (if (= 0 (* (car list) (cadr list)))
            (cons (car list) (sparge (cdr list)))
            (append '(1 2) (sparge (cddr list))
            )))))

(define dothat
  (?(bitisori)
    (if (null? bitisori) '()
        (append (list (bytes->list (car bitisori))) (dothat (cdr bitisori))))))

(dothat (regexp-split #rx"\2+" (list->bytes (sparge l))))

Output.

((0 0 1) (1 0 1) (1 0 1) (1 0 0 1) (1) (0 1 0 1) (0 1 0 1) (0 0 0 1) (1) (0 1) (0 0 1) (1 0 1) ())

Dac? mai ai întreb?ri, te ajut doar dac? îmi explici problemele la ED. Have a nice day.

[actunderdc]

Mersi. Iti dau add pe mess si ti le explic pe ambele.