Haskell, combination with repetitions + permutations

Question

Lets say I have a list with elements, for example [1,2,3,4,5,6,7,8]. I want to create all permutations of this elements with length N.

So, for N = 4 it will be [[1,1,1,1],[1,1,1,2],[1,1,2,1],[1,2,1,1],[2,1,1,1],..] and so on.

comb :: Int -> [a] -> [[a]]
comb 0 _ = [[]]
comb _ [] = []
comb m (x:xs) = map (x:) (comb (m-1) xs) ++ comb m xs

Now, to get this lists first I find all combinations with repetitions for my list, so [[1,1,1,1],[1,1,1,2],[1,1,1,3],[1,1,1,4],[1,1,1,5],...] and for each list I find all permutations and if permutation is not in the list I add it to the list.

permutations1 :: Eq a => [a] -> [[a]]
permutations1 []   = [[]]
permutations1 list = [(x:xs) | x <- list, xs <- permutations1 $ delete1 x list]

delete1:: Eq a => a -> [a] -> [a]
delete1 _ [] = [] 
delete1 a (b:bc) | a == b = bc 
                 | otherwise = b : delete1 a bc

And that's how I get wanted answer.

I understand that it is really(really) bad, but I don't understand haskell enough to write function that will combine these functions.

Answer 1

That is called sampling with replacement. In haskell you may utilize replicateM and monadic behaviour of lists (i.e. non-deterministic computations)

\> import Control.Monad (replicateM)
\> length $ replicateM 4 [1..5]   -- should output 5^4
625
\> replicateM 4 [1..5]
[[1,1,1,1],[1,1,1,2],[1,1,1,3],[1,1,1,4],[1,1,1,5],[1,1,2,1],[1,1,2,2],[1,1,2,3],[1,1,2,4],[1,1,2,5]] ....

If you want to have a sample of size 4 from a population of size 5 with replacement, then for each of the 4 items you have 5 choices; so you are replicating each of the [1..5] 4 times, hence replicateM 4.

The Monad type class (i.e. the M part) says that you should be able to bind these intermediate values together.

The list instance of monad type class models non-determinism. i.e it says that each item is non-deterministic but it can be one of [1..5] values, and to bind them together take an outer product of all the non-deterministic values; because if you have 4 items each taking 5 possible values then you have 5^4 possible final outputs.