Quanta teoria hai studiato? Se hai avuto lezioni sul calcolo lambda, ora è il momento di metterle a frutto.
A questo punto, fermati e ripensa a ciò che hai studiato. Ti ricordi qualcosa sulla ricorsione nel calcolo lambda?
Le specifiche non possono essere soddisfatte da un programma a tempo costante. (Dimostrazione: la dimensione dell'output è superlineare nella dimensione dell'input.) Tuttavia tutte le primitive elencate operano in un tempo costante. Non puoi creare un programma orario non costante con costrutti primitivi a tempo costante.
Ok, quello che ho scritto è vero, ma confuso in questo contesto: i costrutti primitivi forniti dal linguaggio includono più delle funzioni che hai a tua disposizione. Ovviamente la ricorsione consente di scrivere qualsiasi programma computabile da funzioni a tempo costante. Non hai ricorsione qui, comunque. Ma tu hai un'applicazione di funzione. Non è un'operazione a tempo costante - può raggiungere qualsiasi complessità, a seconda della funzione che stai applicando. E puoi creare ricorsione dall'applicazione di funzione.
Questo fa scattare ancora qualche ricordo?
It's called a fixpoint combinator. I'll refer you to your lecture notes or the Wikipedia article for an explanation of how they work. For completeness, here's a definition of a fixpoint combinator in Scheme, for a function that takes one argument:
(define (fix1 phi)
((lambda (rec) (phi (lambda (x) ((rec rec) x))))
(lambda (rec) (phi (lambda (x) ((rec rec) x))))))
Ora puoi definire un iteratore di lista (usando qui una variante a tre argomenti del combinatore del punto di fissazione per chiarezza).
(define foldr
(fix3 (lambda (foldr)
(lambda (f l a)
(if (empty? l) a (f (first l) (foldr f a (rest l))))))))
E immagino tu sappia come andare avanti da lì già.
Un ultimo punto: abbiamo usato define più di una volta. Ma è solo per comodità. Puoi creare fix3 , foldr e qualsiasi altra funzione ausiliaria che potresti aver bisogno di definizioni locali. E poi scrivi la tua singola funzione come applicazione:
(define subsets
((lambda (fix3)
((lambda (foldr it)
(lambda (l) (foldr it '() l)))
(fix3 …)
(lambda (x sets) …)))
(lambda (phi) …)))