[Caml] Esercizio composizione di funzioni parziali

Buonasera a tutti, sono alle prese con un esercizio di programmazione funzionale, ma non riesco proprio a risolverlo. L'esercizio chiede questo: date due funzioni parziali $f:X->Y$ e $g:Y->Z$, implementare la funzione composta così definita: $(f;g)(x)={(g(y) if y = f(x) ^^g(y) downarrow), (uparrow else):}$. Si rappresentano le funzioni parziali come liste di coppie, la funzione è così definita: comp:$ ('axx'b)list -> ('bxx'c)list->('axx'c)list$

Sapreste darmi un suggerimento per implementarla? Il problema sta nel pensarla in termini di programmazione funzionale, ho indicato il linguaggio caml, ma in realtà è indifferente, l'importante è capire l'idea.

EDIT: sono riuscito a scrivere qualcosa che si avvicini alla richiesta, ma c'è un errore che non mi permette di ottenre il tipo giusto:

Codice:

(* comp : ('a * 'b) list -> ('b * 'c) list -> ('a * 'c) list *)

let rec comp l k = function
    [],[] -> []
  | (a, a')::b, (c, c')::d -> if c = a' then (a, c')::comp b d else comp b d;;


La definizione della tua funzione non mi sembra molto chiara. Inoltre quando ottieni un errore che ti blocca è importante scrivere quale sia effettivamente l'errore senza richiedere a chi legge di compilare il tuo codice. Manca comunque sicuramente da considerare il caso in cui una delle liste sia vuota e l'altra no.

L'errore nello specifico è il tipo sbagliato che ottengo: $('axx'b)listxx('bxx'c)list->('axx'c)list$, anzichè $('axx'b)list->('bxx'c)list->('axx'c)list$

Una soluzione che non è language-specific parte dalla constatazione che la composizione di funzioni parziali è la composizione di Kleisli nella categoria di Kleisli della Maybe monad; quindi linguaggi funzionali che implementano una versione di Maybe ready-made rendono la cosa relativamente indolore (Haskell, Agda, Idris lo fanno certamente; credo anche Scala).

Maybe del resto è moto facile da definire da zero, perché si tratta di dire unicamente una cosa come

Codice:

data Maybe a = Nothing | Just a

e a questo punto la composizione di due funzioni parziali \(f : A \to \texttt{Maybe} B\) e \(g : B \to \texttt{Maybe} C\) usa l'estensione di Kleisli di Maybe (>= o come diavolo si scrive).

Ecco, così:

Codice:

comp :: (a -> Maybe b) -> (b -> Maybe c) -> a -> Maybe c
comp f g = (g =<<) . f

Quando si cerca di risolvere problemi di questo tipo è utile partire da un esempio. Supponiamo che la prima funzione parziale sia [("ten", 10); ("one", 1); ("two", 2); ("twenty-two", 22); ("seven", 7)] e che la seconda sia [(15, 6.0); (22, 4.0); (10, 1.0); (7, 7.0)]. Suppongo che l'idea sia quella di ottenere [("ten", 1.0); ("twenty-two", 4.0); ("seven", 7.0)]. È corretto?

Un approccio semplice è il seguente. Per ogni coppia (a, b) della prima lista cerchiamo le coppie (c, d) della seconda lista per cui (b == c). Dopodiché concateniamo le liste corrispondenti. Il seguente codice in Haskell implementa questa idea in un modo spero abbastanza leggibile anche se non conosci bene il linguaggio (visto che usi Caml). Credo che le funzioni filter, map e concatMap siano abbastanza universali e conosciute.

Codice:

comp f g =
  let filtered b = filter (\(c, d) -> (c == b)) g
      fun (a, b) = map (\(c, d) -> (a, d)) (filtered b)
  in concatMap fun f


Vi ringrazio tanto per le risposte. Finalmente ho capito come risolvere!