All possible ways to interleave two strings I recently saw this question on stackoverflow. It's a great question, but there's one fatal problem with the question. They are asking for the best way to do it. E.g, easiest to read, most idiomatic, neatest etc. Don't they know that isn't what matters? You're supposed to ask about how to do it with the fewest bytes of code!

Since I doubt that question will be appreciated on stackoverflow, I decided to ask it here. 

The challenge

You must write the shortest possible program or function that generates all possible ways to interleave any two arbitrary strings. For example, if the two strings are 'ab' and 'cd', the output is:

['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']


As you can see, a is always before b, and c is always before d. 

IO can be in any reasonable format. Use this python code to verify to check your output. (credit: JeD)

def shuffle(s,t):
    if s=="":
        return [t]
    elif t=="":
        return [s]
    else:
        leftShuffle=[s[0]+val for val in shuffle(s[1:],t)]
        rightShuffle=[t[0]+val for val in shuffle(s,t[1:])]
        leftShuffle.extend(rightShuffle)
        return leftShuffle


Sample IO:

shuffle("$", "1234"):
['$1234', '1$234', '12$34', '123$4', '1234$']

shuffle("az", "by"):
['azby', 'abzy', 'abyz', 'bazy', 'bayz', 'byaz']

shuffle("code", "golf"):
['codegolf', 'codgeolf', 'codgoelf', 'codgolef', 'codgolfe', 'cogdeolf', 'cogdoelf',
'cogdolef', 'cogdolfe', 'cogodelf', 'cogodlef', 'cogodlfe', 'cogoldef', 'cogoldfe',
'cogolfde', 'cgodeolf', 'cgodoelf', 'cgodolef', 'cgodolfe', 'cgoodelf', 'cgoodlef',
'cgoodlfe', 'cgooldef', 'cgooldfe', 'cgoolfde', 'cgoodelf', 'cgoodlef', 'cgoodlfe',
'cgooldef', 'cgooldfe', 'cgoolfde', 'cgolodef', 'cgolodfe', 'cgolofde', 'cgolfode',
'gcodeolf', 'gcodoelf', 'gcodolef', 'gcodolfe', 'gcoodelf', 'gcoodlef', 'gcoodlfe',
'gcooldef', 'gcooldfe', 'gcoolfde', 'gcoodelf', 'gcoodlef', 'gcoodlfe', 'gcooldef',
'gcooldfe', 'gcoolfde', 'gcolodef', 'gcolodfe', 'gcolofde', 'gcolfode', 'gocodelf',
'gocodlef', 'gocodlfe', 'gocoldef', 'gocoldfe', 'gocolfde', 'goclodef', 'goclodfe',
'goclofde', 'goclfode', 'golcodef', 'golcodfe', 'golcofde', 'golcfode', 'golfcode']


As usual, standard loopholes apply, and the shortest answer in bytes wins. Since the question was originally about python, I'd love to see the shortest python answer. (And no, pyth is not python). However, answers in any language are encouraged.
Haskell, 53 48 bytes

a%&quot;&quot;=[a]
a%b=[x:t|(x:y,z)&lt;-[(a,b),(b,a)],t&lt;-y%z]

Defines a function % for which a%b with strings a,b gives a list of strings.
Given two strings, we choose one of the two to take the first character from. We then recurse on the remainder of two strings, prepending that character to each result.
When one of the string is empty, the only possible result is the other string. &quot;&quot;%&quot;&quot;=[&quot;&quot;] would also suffice, but's it's longer.

53 bytes:
a@(b:c)%d@(e:f)=((b:)&lt;$&gt;c%d)++((e:)&lt;$&gt;a%f)
a%d=[a++d]

Defines a function % for which a%d with strings a,d gives a list of strings.
The function is defined recursively. If we take a character from the first string, then it must be prepended to each result of the recursive call on the remained of the first string with the second string. Symmetrically for the other string.
For the base case, if one of the strings is empty, the result is a single-element list of their concatenation. This is shorter than two cases for each string being empty.