SCIP in C++11 ― 2.3.3節その1

集合の表現と問題2.59～2.60

シンボルの表現に'をつけるように表示系を書き換え（略）。

まだeq?とequal?をもっと明確に区別すべきか迷う。

区別するのなら、Flyweightパターンの実装が必要なので面倒だなぁ。

だがただでさえ今の実装ではconsと2要素のlistに区別がなく、

数字と数値に区別がないので、段々混乱してきそうで不安・・・。

この節でも触れられていて、問題2.6でも一時悩んだ、

「等しいとはどういうことか」が壁になってきそうな気がしてきたぞ・・・。

isEqualの実装を幅広い比較ができるように変更。

重複を許した場合、adjoin-setは単にconsに、union-setは単にappendになる。

テンプレートパラメターが関係しないときは、

手続きレベルで等しいとしてしまえばいいんだな、そういえば。

----

//equal?

const bool isEqual(const List& list1,

                   const List& list2)

{

    if(isNull(list1) && isNull(list2)){return(true);}

    else if(isNull(list1) || isNull(list2)){return(false);}

    else if(!isPair(list1) && !isPair(list2)){

        return(list1==list2);

    }

    else if(car(list1)!=car(list2)){return(false);}

    return(isEqual(cdr(list1),cdr(list2)));

}

template <typename LeafType>

const bool isEqual(const LeafType& leafItem,

                   const List& x)

{return(isEqual(makeList(leafItem),makeList(x)));}

//---------abstraction barrier---------

//element-of-set?

template<typename ElementType>

const bool isElementOfSet(const ElementType& x,const List& setList)

{

    if(isNull(setList)){return(false);}

    if(isEqual(x,car(setList))){return(true);}

    return(isElementOfSet(x,cdr(setList)));

}

//adjoin-set

template<typename ElementType>

const List adjoinSet(const ElementType& x,const List& setList)

{

    if(isElementOfSet(x,setList)){return(setList);}

    return(cons(x,setList));

}

//intersection-set

const List intersectionSet(const List& set1, const List& set2)

{

    if(isNull(set1)||isNull(set2)){return(makeList());}

    if(isElementOfSet(car(set1),set2)){

        return(cons(car(set1),intersectionSet(cdr(set1),set2)));

    }

    return(intersectionSet(cdr(set1),set2));

}

//union-set

const List unionSet(const List& set1, const List& set2)

{

    if(isNull(set1)){return(set2);}

    if(isElementOfSet(car(set1),set2)){

        return(unionSet(cdr(set1),set2));

    }

    return(cons(car(set1),unionSet(cdr(set1),set2)));

}

template<typename ElementType>

const bool isElementOfMultiSet

(const ElementType& x,const List& setList)

{return(isElementOfSet(x,setList));}

template<typename ElementType>

const List adjoinMultiSet

(const ElementType& x,const List& setList)

{return(cons(x,setList));}

const function<List(List,List)> intersectionMultiSet=

    intersectionSet;

const function<List(List,List)> unionMultiSet=append;

//---------abstraction barrier---------

int main(int argc, char** argv)

{

    const auto set1(makeList("x","+",3));

    const auto element1("+");

    cout<<"(element-of-set? '"<<element1<<" "<<listString(set1)<<") = "

        <<isElementOfSet(element1,set1)<<endl;

    const auto element2("*");

    cout<<"(element-of-set? '"<<element2<<" "<<listString(set1)<<") = "

        <<isElementOfSet(element2,set1)<<endl;

    cout<<"(adjoin-set '"<<element1<<" "<<listString(set1)<<") ="

        <<listString(adjoinSet(element1,set1))<<endl;

    cout<<"(adjoin-set '"<<element2<<" "<<listString(set1)<<") ="

        <<listString(adjoinSet(element2,set1))<<endl;

    const auto set2(makeList(4,"*","x"));

    cout<<"(intersection-set "<<listString(set1)

        <<" "<<listString(set2)<<") = "

        <<listString(intersectionSet(set1,set2))<<endl;

   

    cout<<endl<<"Excersize 2.59:"<<endl;

    cout<<"(union-set "<<listString(set1)

        <<" "<<listString(set2)<<") = "

        <<listString(unionSet(set1,set2))<<endl;

    cout<<endl<<"Excersize 2.60 (multiple set ver.):"<<endl;

   

    cout<<"(adjoin-set '"<<element1<<" "<<listString(set1)<<") ="

        <<listString(adjoinMultiSet(element1,set1))<<endl;

    cout<<"(adjoin-set '"<<element2<<" "<<listString(set1)<<") ="

        <<listString(adjoinMultiSet(element2,set1))<<endl;

    cout<<"(intersection-set "<<listString(set1)

        <<" "<<listString(set2)<<") = "

        <<listString(intersectionMultiSet(set1,set2))<<endl;

    cout<<"(union-set "<<listString(set1)

        <<" "<<listString(set2)<<") = "

        <<listString(unionMultiSet(set1,set2))<<endl;

    return(0);

}

----

出力

----

(element-of-set? '+ ('x '+ 3)) = 1

(element-of-set? '* ('x '+ 3)) = 0

(adjoin-set '+ ('x '+ 3)) =('x '+ 3)

(adjoin-set '* ('x '+ 3)) =('* 'x '+ 3)

(intersection-set ('x '+ 3) (4 '* 'x)) = ('x)

Excersize 2.59:

(union-set ('x '+ 3) (4 '* 'x)) = ('+ 3 4 '* 'x)

Excersize 2.60 (multiple set ver.):

(adjoin-set '+ ('x '+ 3)) =('+ 'x '+ 3)

(adjoin-set '* ('x '+ 3)) =('* 'x '+ 3)

(intersection-set ('x '+ 3) (4 '* 'x)) = ('x)

(union-set ('x '+ 3) (4 '* 'x)) = ('x '+ 3 4 '* 'x)