Exam Check-List: Discussion on Part 03 - Functions Part 2

Benutzeravatar
C0RNi666
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 114
Registriert: 8. Jan 2008 12:51

Exam Check-List: Discussion on Part 03 - Functions Part 2

Beitrag von C0RNi666 »

Follow up with the second part of my solution for possible tasks on the topic of functions.

Feel free to correct me if I'm wrong.

[Spoiler Alert]

Describe the environment (including the environments stored in closures) at certain points in the given program.

The environment is the dynamic context in which certain variables are bound to specific values during runtime. At intitial programm execution, this environment is empty and filled successively with identifier-value combinations while interpreting the sourcecode.

Compute the result of evaluating a given programm with closures.

Code: Alles auswählen

{with {x 3} {fun {y} {+ x y}}}
(fclosure 'y (add (id 'x) (id 'y)) (anEnv 'x (eclosure (num 3) (emptyEnv)) (emptyEnv)))
Give implementation of map, filter, foldl, foldr

Code: Alles auswählen

(define (map f lox)
	(cond 
	[(empty? lox) empty]
	[else (cons (f (first lox)) (map f (rest lox)))]))

(define (filter rel-op th lon) 
	(cond 
		[(empty? lon) empty]
		[else 
			(local ([define f (first lon)]
					[define filtered-rest (filter rel-op th (rest lon))])
					
					(if (rel-op f th)
						filtered-rest
						(cons (first lon) filtered-rest)))
		]
	)
)

(define (foldr combine-op init l)
	(cond 
		[(empty? l) init]
		[else (combine-op (first l) (foldr combine-op init (rest l)))]
	)
)
(define (foldl combine-op init l)
	(cond 
		[(empty? l) init]
		[else (combine-op (foldl combine-op init (rest l)) (first l))]
	)
)
Implement a higher-order function to a given specification

Write a function that consumes a function and two lists and returns a function which applies the input function to members of the input lists with equal indices and outputs a list of the result of this function applictation.

Code: Alles auswählen

(define (zipop f)
  (lambda (l1 l2)
    (if (or (empty? l1) (empty? l2))
        '()
        (cons (f (car l1) (car l2)) ((zipop f) (cdr l1) (cdr l2))))))

Use higher-order functions to implement a programm according to a given specification

Code: Alles auswählen

;; Use "zipop" to implement a function "zipadd" that adds two lists as vectors,
;; i.e. produces a list, the elements of which are sums of the corresponding 
;; elements of the input lists
;;
(define (zipadd lhs rhs)
  ((zipop +) lhs rhs))

Eliminate recursion in the given program by means of standard higher-order functions on lists
Eliminate higher-order functions in the given program by means od recursion

Code: Alles auswählen

 (define (sumList t)
  (foldr + 0 t))
  
 (define (sumList t) 
	(cond 
		[(empty? t) 0]
		[else (+ (first t) (sumList (rest t)))]
	)
)
Et vice versa.


Eliminate "with" expressions in th given program by means of first-class functions

Code: Alles auswählen

 {with {x 3} {fun {y} {+ x y}}}
 {{fun {x} {fun {y} {+ x y}}} 3}
 
 {with {var named} body}) 
 {{fun {var} body} named}
Given a function implemented by recursion, recognize the recursive pattern and make it reusable by implementing corresponding higher-order functions

Code: Alles auswählen

(define (list-of-squares alon)
	(cond
		[(empty? alon) empty]
		[else (cons
			(square (first alon))
			(list-of-squares (rest alon)))]))
			
(define (list-of-squares l) (map square l))
Please comment on this as well.

Regards,

C0RNi666
Win32: Reboot!
Unix: Be root!

Benutzeravatar
sewe
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

Re: Exam Check-List: Discussion on Part 03 - Functions Part

Beitrag von sewe »

C0RNi666 hat geschrieben:

Code: Alles auswählen

(define (foldl combine-op init l)
   (cond
      [(empty? l) init]
      [else (combine-op (foldl combine-op init (rest l)) (first l))]
   )
)
Have a look at your definition of foldl again; there's a bug in there. (Hint: the difference between a left and a right fold is about left- and right-associativity.)

Benutzeravatar
C0RNi666
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 114
Registriert: 8. Jan 2008 12:51

Re: Exam Check-List: Discussion on Part 03 - Functions Part

Beitrag von C0RNi666 »

Of course, you are absolutely right. I admit, I haven't checked my implementation and foldl is not as intuitive as foldr ;)


Here is the correct code:

Code: Alles auswählen

(define (foldl combine-op init l)
   (cond 
      [(empty? l) init]
      [else (foldl combine-op (combine-op (first l) init) (rest l))]
   )
)
Regards,
C0RNi666
Win32: Reboot!
Unix: Be root!

FeG
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 182
Registriert: 6. Dez 2007 07:01

Re: Exam Check-List: Discussion on Part 03 - Functions Part

Beitrag von FeG »

Hi,

9. Describe the environment (including the environments stored in closures) at certain points in the given program.
(I think I understood this marginally different..)

Program:

Code: Alles auswählen

  {with {x 42} {with {f {fun {n} {+ n x}}} {with {x 1} {+ x {f 1}}}}}
Describe environment directly before evaluating expression "{+ 1 {f 1}}":

Code: Alles auswählen

  env = (
    x -> (numb 1),
    f -> (closure: param='n, body=(add (id n) (id x)), env=(x -> 42)),
    x -> (numb 42) -- shadowed by first x mapping)
  )
(Result of evaluation is 1 + (f 1) = 1 + 1 + 42 = 44.)


14. Given an implementation of a higher-order function, tell what it does.
(For the sake of completeness...)

Code: Alles auswählen

(define (foo f tree)
  (cond
    [(empty? tree) empty]
    [(not (cons? tree)) (f tree)]
    [else (cons (foo f (first tree)) (foo f (rest tree)))]))
It's "map for trees".



Best,
Felix

Benutzeravatar
sewe
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

Re: Exam Check-List: Discussion on Part 03 - Functions Part

Beitrag von sewe »

FeG hat geschrieben:9. Describe the environment (including the environments stored in closures) at certain points in the given program.
(I think I understood this marginally different..)

Program:

Code: Alles auswählen

  {with {x 42} {with {f {fun {n} {+ n x}}} {with {x 1} {+ x {f 1}}}}}
Describe environment directly before evaluating expression "{+ 1 {f 1}}":

Code: Alles auswählen

  env = (
    x -> (numb 1),
    f -> (closure: param='n, body=(add (id n) (id x)), env=(x -> 42)),
    x -> (numb 42) -- shadowed by first x mapping)
  )
(Result of evaluation is 1 + (f 1) = 1 + 1 + 42 = 44.)
Yes, that's what we meant by the question: Figure out what's kept in an specific environment at a specific point during program execution. (The above looks good, BTW.)

AlexanderF
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 140
Registriert: 2. Mai 2010 17:55

Re: Exam Check-List: Discussion on Part 03 - Functions Part

Beitrag von AlexanderF »

hello,

I think, there is also a bug in the implementation of filter,
the two cases of if are switched.

(filter odd? (list 1 2 3 4))
is
'(1 3)
not
'(2 4)


and what is the parameter th?
I think filter needs only two parameters
and rel-op only one.

AlexanderF
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 140
Registriert: 2. Mai 2010 17:55

Re: Exam Check-List: Discussion on Part 03 - Functions Part

Beitrag von AlexanderF »

I also want to add,
that in the Haskell implementation of foldl
the parameters of combine-op are inverted
in comparision to the scheme implementation.

so reverse for example can in Haskell be implemented:
foldl (flip (:)) [] l
whereas is scheme there is no flip needed:
(foldl cons empty l)


In foldr there is no such difference between the scheme and Haskell implementation.

Antworten

Zurück zu „Archiv“