I have to implement a function in haskell that takes a list [Int] and gives a list [[Int]] with all permutations, but i'm only allowed to use: [], :, True, False, comparisons, &&, ||, and not
permutations [] = [[]] permutations xs = [(y:zs) | (y,ys) <- picks xs, zs <- permutations ys] where picks (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- picks xs] My idea was to use something like that but i have to replace the <-
As mentioned by chepner in the comments, a few missing elementary library functions can easily be re-implemented “on the spot”.
The Wikipedia article on permutations leads us to, among many other things, the Steinhaus–Johnson–Trotter algorithm, which seems well suited to linked lists.
For this algorithm, an essential building block is a function we could declare as:
spread :: a -> [a] -> [[a]] For example, expression spread 4 [1,2,3] has to put 4 at all possible positions within [1,2;3], thus evaluating to: [[4,1,2,3],[1,4,2,3],[1,2,4,3],[1,2,3,4]]. To get all permutations of [1,2,3,4], you just need to apply spread 4 to all permutations of [1,2,3]. And it is easy to write spread in recursive fashion:
spread :: a -> [a] -> [[a]] spread x [] = [[x]] spread x (y:ys) = (x:y:ys) : (map (y:) (spread x ys)) And permutations can thus be obtained like this:
permutations :: [a] -> [[a]] permutations [] = [[]] permutations (x:xs) = concat (map (spread x) (permutations xs)) Overall, a rules-compliant version of the source code would go like this, with its own local versions of the map and concat Prelude functions:
permutations :: [a] -> [[a]] permutations [] = [[]] permutations (x:xs) = myConcat (myMap (spread x) (permutations xs)) where myMap fn [] = [] myMap fn (z:zs) = (fn z) : (myMap fn zs) myConcat [] = [] myConcat ([]:zss) = myConcat zss myConcat ((z:zs):zss) = z : (myConcat (zs:zss)) spread z [] = [[z]] spread z (y:ys) = ( z:y:ys) : (myMap (y:) (spread z ys)) 
<-is not a function, it is part of the list comprehension syntax (i.e. the[ ... | ... <- ... ]). I would ask if you are allowed to use list comprehensions. I assume that some other syntactic constructs are allowed as well, like=andwhere, but those are admittedly more fundamental than list comprehensions.letexpressions andconcatMap(which, if you can't use, is easily reimplemented in as low-level detail as fits your constraints).