recursionsmlcompositionml

Composistion in SML (Discreate Math and Functional Programming)


I need to define a recursive ML function composition that accepts two relations and returns the composition of the two relations. I need to use the thhisIsTheImageOf and createRelationFromImage function in my definition of composition.

Here is the code that is needed to be used to define the composition

fun thisIsTheImageOf(e,[])=[]
    |thisIsTheImageOf(e,(a,b)::xs) = 
        if e=a 
        then b::thisIsTheImageOf(e,xs)
        else thisIsTheImageOf(e,xs);

Here are the datatype, value, and tested inputs for the thisIsTheImageOf function

datatype city =Vancouver|LosAngeles|Mexico|Minneapolis|Omaha |KansasCity|Denver|StLouis|Memphis|Chicago |NewOrleans|Cinncinati|Pittsburgh|Montreal|NewYork;

datatype rivers =Missouri|Platte|NPlatte|SPlatte|Arkansas|Canadian |Kansas|Mississippi|Tennessee|Ohio|Allegheny|Monongahela;

val isOnRiver=[(Denver,Platte),(Omaha,Missouri),(Omaha,Platte),(KansasCity,Missouri),(KansasCity,Kansas),(Minneapolis,Mississippi),(StLouis,Mississippi),(StLouis,Mi vssouri),(Memphis,Mississippi),(NewOrleans,Mississippi),(Cinncinati,Ohio),(Pittsburgh,Ohio),(Pittsburgh,Allegheny),(Pittsburgh,Monongahela)];

val flowsInto=[(Platte,Missouri),(Kansas,Missouri),(Missouri,Mississippi),(Allegheny,Ohio),(Monongahela,Ohio),(Tennessee,Ohio),(NPlatte,Platte),(SPlatte,Platte),(Ohio,Mississippi)];

thisIsTheImageOf(Pittsburgh, isOnRiver);thisIsTheImageOf(Mississippi, flowsInto);thisIsTheImageOf(Cinncinati, isOnRiver);

fun createRelationFromImage(e,[])=[]
createRelationFromImage(e,x::xs)= (e,x)::createRelationFromImage(e,xs);``

Here are tested inputs for the createRelationFromImage function
createRelationFromImage("Cincinnati",["New York", "Boston", "Dallas"]);

These two functions were created as a separate function but I am supposed to use the two functions to make a recursive function of composition.

I know the composition function mathematically and here is what I put as to help me see what I need to do

fun composition( i, r)x=i(r(x));

however, I am stuck on going further when trying to implement the two functions.


Solution

  • fun composition([],_ )=[]
    | composition((a,b)::rest,relation)=
        let 
        fun thisIsTheImageOf(e,[])=[]
        |thisIsTheImageOf(e,(a,b)::xs) = 
            if e=a 
            then b::thisIsTheImageOf(e,xs)
            else thisIsTheImageOf(e,xs);
        fun createRelationFromImage(e,[])=[]
        | createRelationFromImage(e,x::xs)= (e,x)::createRelationFromImage(e,xs);
    in 
     createRelationFromImage(a, (thisIsTheImageOf(b, relation)))@ composition(rest, relation)
     end;