Funzioni di ordine superiore

Vedi tutte le pagine e le modifiche recenti o scarica i sorgenti nella pagina


Cosa e’ una Funzione di Ordine Superiore (Higher Order Function)? Una funzione di ordine superiore e’ una funzione che manipola dei dati speciali.. delle altre funzioni :)

Prima di addentrarvi nella lettura fareste bene a leggere l’introduzione agli oggetti funzione

Si parla molto spesso di astrazione riferendosi ad un buono stile di programmazione.

Ad esempio, dovendo scrivere funzioni per calcolare il doppio di 3 e 4, questo stile:
 def doppio_3
  6
 end
 def doppio_4
  8
 end
Sarebbe considerato straordinariamente stupido. La soluzione corretta sarebbe: conservare la logica in un punto, e lasciare la definizione dei dati all’utente:
 def doppio(num)
  num*2
 end

Nei linguaggi che permettono la manipolazione di funzioni, e’ facile arrivare all’idea che anche alcune parti della logica possono essere definite dall’utente. Ad esempio, volendo scrivere un sistema che cerchi un libro in una biblioteca:

stile idiota:
 def cerca_promessi_sposi
  return promessi_sposi
 end
 def cerca_divina_commedia
  return divina_commedia
 end
 ...
stile normale:
 def cerca_per_titolo(titolo)
  for i in libri
   return i if i.titolo=titolo
  end
 end

 def cerca_per_ISBN(codice)
  for i in libri
   return i if i.isbn=codice
  end
 end
 ...
stile funzionale, piu’ astratto:
 def cerca_per(funzione_chiave)
  for i in libri
   return if funzione_chiave(i)
  end
 end
I sistema iteratori/blocchi in ruby serve esattamente a questo scopo. Esempi classici sono map() , find(), sort_by()..

Le trasformazioni e le funzioni di analisi che possiamo applicare ad un Enumerable con queste funzioni.. sono infinite. D’altronde, riempire il blocco con una decina di funzioni puo’ risultare in codice poco chiaro, o poco elegante. La soluzione funzionale e’ la generazione di altre funzioni Vediamo un esempio d’uso di reject(), che funziona esattamente al contrario di select()

Nota: usiamo degli oggetti Proc invece di normali funzioni.

 >> lunga= proc do |x|
 ?>  x.length > 5
 >> end
 => #<Proc:0x401e9df0@(irb):1>
 >>
 ?> numerica=proc do |linea|
 ?>  /[0-9]/.match(linea)
 >> end
 => #<Proc:0x401e5908@(irb):5>
 >>  puts  File.new('esempio.txt').reject(&lunga).reject(&numerica)
 => nil
 >>  puts  File.new('esempio.txt').reject(&lunga).select(&numerica)
 la 3
 => nil
Visto come abbiamo combinato reject() e find_all() ? Possiamo farlo infinite volte, fino a scrivere linee anche molto complesse. Per evitare di scrivere codice completamente incomprensibile, puo’ essere una buona idea usare delle funzioni generate al volo come composizione di altre. Una funzione che manipoli altre funzioni invece di comuni dati viene detta Higher Order Function, cioe’ funzione di ordine superiore. Come esempio, scriviamo both(x,y) che accetta in input due funzioni semplici e ne restituisce una nuova, combinazione di entrambe (both, appunto):
 both= proc do |funz_a,funz_b|
        proc do |x|
         funz_a[x] and funz_b[x]
        end
      end

 lunga= proc do |x|
        x.length > 5
       end

 numerica= proc do |linea|
           /[0-9]/.match(linea)
          end

 lung_num=both[lunga,numerica]

 puts File.new('esempio.txt').select(&lung_num)  

Con le HFO potete modellare problemi anche molto complessi mantenendo sempre una buona chiarezza descrittiva. In ruby non le userete molto, poiche’ che i blocchi in ruby rendono particolarmente naturale scrivere la funzione “al volo”. e rendono meno intuitive le HFO. Perche’ invece in LISP, ad esempio, cio’ rimane piu’ naturale? Semplice, perche’ i blocchi in ruby rappresentano una Forma Lambda, e mentre in lisp e’ piu’ semplice combinare funzioni che scrivere forme lambda ogni volta, in ruby e’ il contrario. Ad ogni modo, e’ interessante notare che il meccanismo di ruby nasce proprio come evoluzione di quello di LISP/Scheme, unito al meccanismo dei blocchi di SmallTalk.

Anche se ruby non e’ un linguaggio funzionale, e’ affascinante vedere quanto possa essere flessibile. Vediamo un esempio. Supponiamo di avere un file strutturato in questa maniera:
 #nome matricola anno_di_nascita sesso
 Gabriele 09101234 1980 M
 Elena 12120987 1986 F
 Nicola 12543211 1985 M
 Filippo 98762211 1953 M
 # commenti che iniziano per #
 Lorenzo 62617171 1990 M
 Costanza 01919111 1970 F
 Silvia 12679012 1979 F
 #Silvia 12679012 1079 F

Dobbiamo scrivere un programma che trovi tutte le femmine nate prima del 1980 e tutti i maschi nati dopo o nel 1980, ovviamente ignorando le linee di commento, cioe’ quelle che cominciano con un ”#”. Dunque, ragioniamo per gradi:

abbiamo bisogno di una funzione che identifichi le linee commentate: is_comm() di due funzioni per il sesso: is_M() e is_F() di una per i nati prima del 1980 is_pre_1980() e di una per i nati dopo il 1979 is_post_1979() Tranquilli, e’ piu’ semplice di quel che sembra usando reject(), find_all() e map() (usiamo anche delle piccole HOF generiche..)
 # le nostre funzioncine di ordine superiore, le aggiungiamo come
 # metodi della classe Proc                
 class Proc
  def not!
   proc do |x|
    not self[x]
   end
  end

  def and(fun_b)
   proc do |x|
    self[x] and fun_b[x]
   end
  end

  def or(fun_b)
   proc do |x|
    self[x] or fun_b[x]
   end
  end
 end
Queste sono funzioni generali, che secondo me sono comode, ma delle quali si puo’ fare a meno.. ed ecco il codice effettivo:
 is_comm     = proc { |linea| linea[0].chr == '#' }
 is_M        = proc { |lin|  lin[-2].chr == 'M' }
 pre_1980    = proc { |lin| (lin.split[2]).to_i  < 1980 }

 is_F        = is_M.not!
 post_1980   = pre_1980.not!

 ok          = is_F.and(pre_1980).or is_M.and(post_1980)

 puts File.new('dati.txt').reject(&is_comm).find_all(&ok)

La versione imperativa sarebbe: 

 res=[]
 f=File.new('dati.txt')
  for l in f do
   if not l[0].chr =='#'
    if l[-2].chr == 'M'
    if l.split[2].to_i>=1980
      res.push(l)
     end
    else
     if l.split[2].to_i> 1980
      res.push(l)
     end
    end
   end
 end

 f.close
 puts  res

A voi la decisione su quale approccio sia piu’ chiaro, e meno propenso a farvi commettere errori. Avete scelto? Ora cercate di capire che modifiche accadrebbero se doveste aggiungere una funzione che restituisca maschi e femmine nati prima del 1980 e con matricola che inizia per ‘091’. Quale approccio vi sembra migliore? Ovviamente siete liberi di scegliere un approccio ibrido ;).

Un ultima nota: noi abbiamo definito delle funzioni di ordine superiore molto semplici, ma si possono definire strutture molto complesse. Se ne avete voglia sarebbe interessante un poorting delle funzioni definite in OnLisp, anche se potreste scoprire che ruby include gia’ parecchio del Common LISP :-)

— Un’esempio di HOF piuttosto utile: memoize

Created on November 25, 2005 16:28 by Ruby Fan (151.37.134.237)