Scala permute list (recursive type mismatch)

Question

I have the following code:

      type foo= List[bar]
      def emtfoo= List[bar]()

   def permute(s1:Set[foo],s2:Set[foo]):Set[foo]={
     for{ 
        x<-s1
        y<-s2 
     }yield permutatefoo(x,y,e,emtfoo)

def permutatefoo(l1:foo,l2:foo,sofar:foo):Set[foo]={
    if (l1.equals (emtfoo)) {
       Set{sofar:+l2}
      }
    else {
    combine(permutatefoo(l1.drop(1),l2,l1.take(1):::sofar),
        permutatefoo(l1,l2.drop(1),l2.take(1):::sofar))
        }
    }
def combine(s1:Set[foo],s2:Set[foo]):Set[foo] = 
   for {
      x <- s1
      y<- s2
  } yield x ::: y

Which should be fairly straightforward code to permutate 2 sets of lists into a single set which has all possible permutations of both lists in order with no element appearing in front of an element in wasn't in front of in the list itself (so if we have list a = 1,2,3 and list b =a,b,c then it should return the Set{1,a,2,b,3,c-1,2,a,3,b,c-a,1,2,3,b,c ext.}). However my code generates a few errors type mistmaches around the line.

{Set{sofar:+l2}}

and

   x<-s1

Does anybody know how to fix this?

Answer 1

I'm not sure I grok all your code, but a few things I see are:

1:

{Set{sofar:+l2}} // should probably be Set(sofar ++ l2)
                 // as it seems you just want to concatenate sofar and l2 
                 // which are both List[bar] (so your return value is a Set[foo]
                 // i.e. a Set[List[bar]] as the signature for 
                 // permutatefoo requests

:+ is an extractor (see the doc) and it's not supposed to be used in that way

2:

if (l1.equals (emtfoo)) // you should also check against ls.equals(emtfoo)
                        // as you're also dropping elements from l2
                        // in permutatefoo(l1,l2.drop(1),l2.take(1):::sofar))

3:

the return type for permute is wrong. The way you defined it, it returns a Set[Set[foo]] instead of a Set[foo]. I'm not sure I understand what you want it to do, but if you fix the return type it should at least type-check.

---

This is a version of your code that compiles. I'm not saying it works (as I said, I'm not sure I understand what all the expected inputs and outputs for your program should be), but it compiles.

type bar=Int

type foo= List[bar]
def emtfoo= List[bar]()

def combine(s1:Set[foo],s2:Set[foo]) = 
   for{
      x <- s1
      y <- s2
  } yield x ++ y

def permutatefoo(l1:foo, l2:foo, sofar:foo): Set[foo]={
    if (l1.equals (emtfoo) || l2.equals (emtfoo)) {
       Set(sofar ++ l2)
      }
    else
    {
    combine(permutatefoo(l1.drop(1),l2,l1.take(1) ++ sofar),
        permutatefoo(l1,l2.drop(1),l2.take(1) ++ sofar))
    }
}

def permute(s1:Set[foo],s2:Set[foo]) : Set[Set[foo]] = {
     for { 
        x <- s1
        y <- s2 
     } yield permutatefoo(x,y,emtfoo)
}